[Codeforces Round 1004(Div.2)] - D. Object Identification

https://codeforces.com/contest/2067/problem/D

Codeforces Round 1004(Div.2)] - D. Obejct Identification

문제 유형: 그래프, 생성형, 인터랙티브

시간 제한: 2초

메모리 제한: 256MB

 

문제

This is an interactive problem.

You are given an array x1,…,xn of integers from 1 to n. The jury also has a fixed but hidden array y1,…,yn of integers from 1 to n. The elements of array y are unknown to you. Additionally, it is known that for all i, xi≠yi, and all pairs (xi,yi)

are distinct.

The jury has secretly thought of one of two objects, and you need to determine which one it is:

• Object A: A directed graph with n vertices numbered from 1 to n, and with n edges of the form xi→yi.

• Object B: n points on a coordinate plane. The i-th point has coordinates (xi,yi).

 

To guess which object the jury has thought of, you can make queries. In one query, you must specify two numbers i,j

(1≤i,j≤n,i≠j).

In response, you receive one number:

• If the jury has thought of Object A, you receive the length of the shortest path (in edges) from vertex i to vertex j in the graph, or 0 if there is no path.

• If the jury has thought of Object B, you receive the Manhattan distance between points i and j, that is |xi−xj|+|yi−yj|.

 

You have 2 queries to determine which of the objects the jury has thought of.

 

당신은 1 ~ n까지의 범위의 수를 가지는 x1, ... xn배열을 가집니다.

심사위원은 y1, ... yn의 배열까지 가지고 있습니다. 이것 역시 1 ~ n중에서 값을 가집니다.

y 배열의 값을 당신은 알 수 없습니다.

추가적으로, 모든 요소에서 xi != yi이고, 모든 페어 (xi, yi)는 독립적입니다.(중복이 없습니다.)

심사위원은 두 가지의 객체 중 하나를 가지고 있습니다.

• 객체 A: 1에서 n까지 라벨이 붙은 방향 그래프. xi -> yi의 간선 n개로 구성됩니다.
• 객체 B: 좌표평면에서의 n개의 점. i번째 점은 (xi, yi)입니다.

당신은 쿼리를 날릴 수 있습니다.

두 인덱스 정수 i, j를 질의할 수 있습니다.

응답으로, 하나 답을 받습니다:

• 심사위원이 A를 가진 경우, 정점 i에서 j까지의 최단거리를 반환합니다. 도달할 수 없으면, 0을 반환합니다.
• 심사위원이 B를 가질 경우, 두 정점 간의 맨해튼 거리(|xj-xi| + |yj-yi|)를 반환합니다.

당신은 최대 2회의 쿼리를 사용가능합니다.

 

입력

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤1000). The description of the test cases follows.

 

첫째 줄에 테스트 케이스의 개수 t가 주어집니다.

각 테스트 케이스별로 아래의 인터랙션이 시작됩니다.

 

인터랙션

The interaction begins with reading n (3≤n≤2⋅105) — the length of the arrays x and y

at the start of each test case.

Next, read n integers: x1,x2,…,xn (1≤xi≤n) — the elements of array x .

It is guaranteed that the sum of n across all test cases does not exceed 2⋅10^5.

The array y1,y2,…,yn is fixed for each test case. In other words, the interactor is not adaptive.

It is guaranteed that xi≠yi for all 1≤i≤n, and all pairs (xi,yi) are distinct.

To make a query, output "? i j" (without quotes, 1≤i,j≤n,i≠j ).

Then you must read the response to the query, which is a non-negative integer.

To give an answer, output "! A" if Object A is hidden or "! B" if Object B is hidden (without quotes).

Note that printing the answer does not count as one of the 2 queries.

After printing each query do not forget to output the end of line and flush∗ the output. Otherwise, you will get Idleness limit exceeded verdict. If, at any interaction step, you read −1 instead of valid data, your solution must exit immediately. This means that your solution will reveive Wrong answer because of an invalid query or any other mistake.

Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream. Note that if the query is correct, the response will never be −1.

 

인터랙션은 다음으로 시작합니다:

첫째 줄에 n이 주어지고,

둘째 줄에 x배열의 요소들이 주어집니다.

y배열의 정보는 알 수 없습니다.

 

쿼리를 보내려면, "? i j"를 출력하시오. (i, j는 인덱스 정수) 그 뒤 응답을 표준입력으로 하나 받으시오.

정답을 제출하려면, "! A" 또는 "! B"를 출력하시오.

 

응답을 받기 위해, 출력 후 flush하는 것을 잊지 마시오.

쿼리가 유효하지 않으면, -1을 반환합니다.

 

풀이

Editorial: https://codeforces.com/blog/entry/139415?locale=en

두 가지의 케이스가 있다.

 

1) x배열에 1~n이 정확히 하나씩 있는 경우

여러 케이스를 따져봐야 한다.

x배열에서 1을 가진 인덱스와 n을 가진 인덱스를 찾는다. 각각 i1, in이라 하자.

쿼리 "? i1 in"을 날린 응답에 대해서 1차적으로 판단할 수 있다.

만약 응답이 n-1보다 작은 경우, 반드시 'A'이다.

  왜냐하면 'B'인 경우, 쿼리에서 x축 면에서의 차가 n-1이다.

  즉, 맨해튼 거리이려면 응답은 n-1이상이여야 한다.

만약 응답이 n-1보다 큰 경우, 반드시 'B'이다.

  왜냐하면 그래프인 경우, 두 노드 간 최단 거리의 상한은 n-1이기 때문이다.

만약 응답이 정확히 n-1인 경우, 추가 쿼리를 한번 더 날려본다. 반대로 쿼리를 날려본다. "? in, i1" 이렇게 날리면 된다.

  추가 쿼리의 응답 역시 n-1인 경우, 'B'이다. 쿼리의 순서가 바뀌어도 맨해튼 거리는 변하지 않기 떄문이다.

  게다가, A인 경우, 추가 쿼리의 응답은 1 또는 0이 나올 것이다. 이미 1 -> n에서 n-1개의 간선을 소모했으니, n -> 1로 가려면 간선 하나만 써야 한다. 또는, n에서 1로 도달하지 못하여 응답이 0이 될 수 있다.

 

2) 그렇지 않은 경우

만약 그래프라면, 문제 조건인 xi != yi와 페어가 중복되지 않는다는 것 때문에, x배열에 등장한 적 없는 노드에서 쿼리를 날리면, 반드시 0이 나와야 한다.

즉, x배열에 등장한 적 없는 노드와 아무 다른 노드 하나에 쿼리를 날려서 0이 나오면 'A', 아니면 'B'가 정답이다.

 

코드

C++

#include <bits/stdc++.h>
#include <numeric>

using namespace std;

void solve() {
  int n;
  cin >> n;
  vector<int> x(n + 1), isx(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> x[i];
    isx[x[i]] = 1;
  }

  // if permutation
  if (accumulate(isx.begin(), isx.end(), 0) == n) {
    int i1 = 0, in = 0;
    for (int i = 1; i <= n; ++i) {
      if (x[i] == 1)
        i1 = i;
      if (x[i] == n)
        in = i;
    }
    cout << "? " << i1 << " " << in << endl;
    int ans;
    cin >> ans;
    if (ans < n - 1) {
      cout << "! A" << endl;
    } else if (ans > n - 1) {
      cout << "! B" << endl;
    } else {
      cout << "? " << in << " " << i1 << endl;
      cin >> ans;
      if (ans == n - 1) {
        cout << "! B" << endl;
      } else {
        cout << "! A" << endl;
      }
    }
  } else {
    for (int i = 1; i <= n; ++i) {
      if (!isx[i]) {
        cout << "? " << i << " " << 1 + (i == 1 ? 1 : 0) << endl;
        int ans;
        cin >> ans;
        if (ans == 0) {
          cout << "! A" << endl;
        } else {
          cout << "! B" << endl;
        }
        return;
      }
    }
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--)
    solve();

  return 0;
}