| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 20 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 258 | 48 | 36 | 20.339% |
This is an interactive problem.
It is time for the Sogang Computer Science Festival (Korean: 서강대학교 컴퓨터공학과 전산제). $N$ people gathered to congratulate the remarkable anniversary of the Department of Computer Science and Engineering.
There is a rumor that a celebrity has come to this festival. You, curious about who the celebrity is, are tasked with finding a celebrity among the $N$ people at this festival.
A celebrity is someone known by everyone at this festival who does not know anyone else. You can roam around the festival venue to ask if some person $A$ knows some other person $B$. By asking at most $Q$ questions, determine whether this festival has a celebrity and, if so, identify who it is.
Initially, two space-separated integers are given: $N$, which denotes the number of attendees to this festival, and $Q$, which denotes the number of questions you can ask. ($1 \le N \le 100\,000;$ See below for $Q$)
You can interact with the judging system by outputting one of the following:
? $A$ $B$: Ask if the person $A$ knows $B$. ($1 \le A,B \le N;$ $A \ne B$) This type of interaction can be made at most $Q$ times.
1 if the person $A$ knows $B$, or 0 if they don't.! $X$: If $X \ne -1$, identify the celebrity as person $X$. Otherwise, conclude that there is no celebrity in this festival.
You should also output a newline character and flush the standard output buffer. Failure to adhere to any of these requirements can result in an unexpected verdict.
In this subtask, $Q=N^2$.
Modified constraints apply: $1 \le N \le 400$.
In this subtask, $Q=3N$.
Original constraints apply: $1 \le N \le 100\,000$.
4 16 0 1 0 1 0 1 1
? 1 2 ? 2 1 ? 1 3 ? 3 1 ? 1 4 ? 4 1 ! 1
(For Sogang students:) Note that this problem is an improvised version that matches the format of a problem in a general programming contest. While in the exam, the original scoring was:
University > 서강대학교 > CSE4152 문제해결프로그래밍실습 > 2024-2학기 중간고사 코딩 테스트 1번