codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2066A.md (4237B)


      1 Source: https://codeforces.com/problemset/problem/2066/A
      2 
      3 A. Object Identification
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 This is an interactive problem.
     22 
     23 You are given an array $x_1, \ldots, x_n$ of integers from $1$ to $n$. The jury also has a fixed but hidden array $y_1, \ldots, y_n$ of integers from $1$ to $n$. The elements of array $y$ are unknown to you. Additionally, it is known that for all $i$, $x_i \neq y_i$, and all pairs $(x_i, y_i)$ are distinct.
     24 
     25 The jury has secretly thought of one of two objects, and you need to determine which one it is:
     26 
     27 * Object A: A directed graph with $n$ vertices numbered from $1$ to $n$, and with $n$ edges of the form $x_i \to y_i$.
     28 * Object B: $n$ points on a coordinate plane. The $i$-th point has coordinates $(x_i, y_i)$.
     29 
     30 To guess which object the jury has thought of, you can make queries. In one query, you must specify two numbers $i, j$ $(1 \leq i, j \leq n, i \neq j)$. In response, you receive one number:
     31 
     32 * 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.
     33 * If the jury has thought of Object B, you receive the Manhattan distance between points $i$ and $j$, that is $|x_i -x_j| + |y_i - y_j|$.
     34 
     35 You have $2$ queries to determine which of the objects the jury has thought of.
     36 
     37 Input
     38 
     39 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.
     40 
     41 Interaction
     42 
     43 The interaction begins with reading $n$ ($3 \leq n \leq 2 \cdot 10^5$) — the length of the arrays $x$ and $y$ at the start of each test case.
     44 
     45 Next, read $n$ integers: $x_1, x_2, \ldots, x_n$ ($1 \leq x_i \leq n$) — the elements of array $x$.
     46 
     47 It is guaranteed that the sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.
     48 
     49 The array $y_1, y_2, \ldots, y_n$ is fixed for each test case. In other words, the interactor is not adaptive.
     50 
     51 It is guaranteed that $x_i \neq y_i$ for all $1 \leq i \leq n$, and all pairs $(x_i, y_i)$ are distinct.
     52 
     53 To make a query, output "? $i$ $j$" (without quotes, $1 \le i, j \le n, i \neq j$). Then you must read the response to the query, which is a non-negative integer.
     54 
     55 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.
     56 
     57 After printing each query do not forget to output the end of line and flush$^{\text{∗}}$ 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$.
     58 
     59 Hacks
     60 
     61 The first line must contain an integer $t$ ($1 \le t \le 1000$) — the number of test cases.
     62 
     63 The first line of each test case must contain an integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the length of the hidden array.
     64 
     65 The second line of each test case must contain $n$ integers — $x_1, x_2, \ldots, x_n$ ($1 \le x_i \le n$).
     66 
     67 The third line of each test case must contain $n$ integers — $y_1, y_2, \ldots, y_n$ ($1 \le y_i \le n$).
     68 
     69 It must be ensured that $x_i \neq y_i$ for all $1 \le i \le n$, and all pairs $(x_i, y_i)$ must be distinct.
     70 
     71 The fourth line must contain one character: A or B, indicating which of the objects you want to hide.
     72 
     73 The sum of $n$ across all test cases must not exceed $2 \cdot 10^5$.
     74 
     75 $^{\text{∗}}$To flush, use:
     76 
     77 * fflush(stdout) or cout.flush() in C++;
     78 * sys.stdout.flush() in Python;
     79 * see the documentation for other languages.
     80 
     81 Example
     82 
     83 Input
     84 
     85 ```
     86 2
     87 3
     88 2 2 3
     89 
     90 1
     91 
     92 0
     93 
     94 5
     95 5 1 4 2 3
     96 
     97 4
     98 
     99 4
    100 ```
    101 
    102 Output
    103 
    104 ```
    105 ? 2 3
    106 
    107 ? 1 2
    108 
    109 ! A
    110 
    111 ? 1 5
    112 
    113 ? 5 1
    114 
    115 ! B
    116 ```
    117 
    118 Note
    119 
    120 In the first test case, $x = [2,2,3]$, $y = [1,3,1]$ and Object A is guessed.
    121 
    122 In the second test case, $x = [5,1,4,2,3]$, $y = [3,3,2,4,1]$ and Object B is guessed.