QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#882969 | #9734. Identify Chord | fairyqq28 | TL | 0ms | 0kb | C++14 | 1.2kb | 2025-02-05 14:04:41 | 2025-02-05 14:04:41 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cassert>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
int qry(int x, int y){
printf("? %d %d\n", x+1, y+1); fflush(stdout);
int ret; scanf("%d", &ret); return ret;
}
int n, x, y, d, p, k;
void solve(){
scanf("%d", &n);
x = 0, y = n / 2;
for(int t = 0; ; t ^= 1){
d = qry(x, y);
if(d < n / 2) break;
if(!(n & 1)) x++, y++;
else if(t) x++;
else y++;
}
int dl = qry((x+n-1)%n, y), dr = qry((x+1)%n, y);
if(dl >= d && dr >= d) p = x, k = d-1;
else if(dl < d){
int l = 1, r = n/2 - 1, t = -1;
while(l <= r){
int mid = (l+r)>>1;
if(qry((x+n-mid)%n, y) == d - mid) t = mid, l = mid + 1;
else r = mid - 1;
}
assert(~t);
p = (x+n-t)%n, k = d-t-1;
}
else{
int l = 1, r = n/2 - 1, t = -1;
while(l <= r){
int mid = (l+r)>>1;
if(qry((x+mid)%n, y) == d - mid) t = mid, l = mid + 1;
else r = mid - 1;
}
p = (x+t)%n, k = d-t-1;
}
if(qry(p, (y+k)%n) == 1) printf("! %d %d\n", p+1, (y+k)%n+1);
else printf("! %d %d\n", p+1, (y+n-k)%n+1);
fflush(stdout);
}
int main(){
int T; scanf("%d", &T); while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
input:
2 6 2 2 1 1 1 1 1 4 0 1 0 1 0 1 0
output:
? 1 4 ? 6 4 ? 2 4 ? 2 4 ? 3 4 ? 2 4 ! 2 4 ? 1 1 ? 1 2 ? 2 2 ? 2 3 ? 3 3 ? 3 4 ? 4 4 ? 4 5 ? 5 5