QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#883987 | #9734. Identify Chord | Estelle_N | WA | 0ms | 1664kb | C++14 | 1.7kb | 2025-02-05 20:30:56 | 2025-02-05 20:31:06 |
Judging History
answer
#include <cstdio>
#include <algorithm>
using namespace std;
int T, n;
int ask(int x, int y, int z = 0)
{
printf("? %d %d\n", x, y);
fflush(stdout);
scanf("%d", &z);
return z;
}
void ans(int x, int y, int z = 0)
{
printf("! %d %d\n", x, y);
fflush(stdout);
scanf("%d", &z);
}
void work()
{
scanf("%d", &n);
if(n <= 8)
{
for(int i = 1; i <= 8; ++ i)
for(int j = i + 1; j <= 8; ++ j)
if(ask(i, j) == 1)
return ans(i, j);
}
int u = 1, v = n / 2 + 1, w = n / 2, d = ask(u, v);
while(d == w)
{
if(n & 1)
{
if(w == n / 2)
++ v, ++ w;
else
++ u, -- w;
}
else
++ u, ++ v;
d = ask(u, v);
}
if(d == 1)
return ans(u, v);
int delta = w - d;
int x = u + 1, y = v, z = y - x, k = ask(x, y);
if(k == 1)
return ans(x, y);
if(z - k == delta)
u = x, v = y, w = z, d = k;
else
{
(-- u == 0) && (u = n);
if(u > v)
swap(u, v);
w = v - u, d = w - delta;
if(d == 1)
return ans(u, v);
}
int l = u, r = v - delta - 1;
while(l <= r)
{
int mid = l + r >> 1;
if(v - mid - ask(mid, v) == delta)
r = mid - 1, x = mid;
else
l = mid + 1;
}
y = (x + delta + 1) % n;
if(!y)
y = n;
if(ask(x, y) != 1)
{
y = ((x - delta - 1) % n + n) % n;
if(!y)
y = n;
}
ans(x, y);
}
int main()
{
scanf("%d", &T);
while(T --)
work();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 1664kb
input:
2 6 1 -1
output:
? 1 2 ! 1 2
result:
wrong answer Wrong answer n=6, actual=2-4, guessed=1-2 (test case 1)