QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#882969#9734. Identify Chordfairyqq28TL 0ms0kbC++141.2kb2025-02-05 14:04:412025-02-05 14:04:41

Judging History

This is the latest submission verdict.

  • [2025-02-05 14:04:41]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2025-02-05 14:04:41]
  • Submitted

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

result: