QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#882536#9734. Identify ChordHildaHuWA 25ms3584kbC++141.8kb2025-02-05 09:06:482025-02-05 09:06:48

Judging History

This is the latest submission verdict.

  • [2025-02-05 09:06:48]
  • Judged
  • Verdict: WA
  • Time: 25ms
  • Memory: 3584kb
Show
  • [2025-02-05 09:06:48]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

int T, n, dis, res;
bool flag;
int query(int x, int y) {
	x = (x - 1) % n + 1, y = (y - 1) % n + 1;
	if (flag) x = n + 1 - x, y = n + 1 - y;
	cout << "? " << x << " " << y << endl;
	int tmp; cin >> tmp;
	return tmp;
}
void ans(int x, int y) {
	if (flag) x = n + 1 - x, y = n + 1 - y;
	cout << "! " << x << " " << y << endl;
	cin >> res;
	if (res == -1) exit(0);
}
int getx(int x, int y) {
	int l = x, r = y, ret = -1;
	if (l > r) r += n;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (query(mid, y) == dis - (mid - x)) ret = mid, l = mid + 1;
		else r = mid - 1;
	}
	return (ret - 1) % n + 1;
}
void solve1(int x, int y) {
	int retx = getx(x, y), rety = -1;
	int l = retx, r = y;
	if (l > r) r += n;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (query(x, mid) == dis - (y - mid + n) % n) rety = mid, r = mid - 1;
		else l = mid + 1;
	}
	ans(retx, (rety - 1) % n + 1);
}
void solve2(int x, int y) {
	int retx = getx(x, y), rety = -1;
	int l = y, r = x;
	if (l > r) r += n;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (query(x, mid) == dis - (mid - y)) rety = mid, l = mid + 1;
		else r = mid - 1; 
	}
	ans(retx, (rety - 1) % n + 1);
}
bool work(int x, int y) {
	dis = query(x, y);
	if (dis == n / 2) return false;
	bool dx = query(x + 1, y) == dis - 1;
	bool dy = query(x, y + 1) == dis - 1;
	if (dx && !dy) solve1(x, y);
	else if (!dx && dy) solve1(y, x);
	else if (dx && dy) solve2(x, y);
	else flag = true, solve2(n + 1 - x, n + 1 - y);
	return true;
}

int main() {
	cin >> T;
	while (T--) {
		cin >> n; flag = false;
		int x = 1, y = x + n / 2;
		while (!work(x, y)) {
			if (n & 1) {
				if ((y - x + n) % n == n / 2 + 1) x = x % n + 1;
				else y = y % n + 1;
			} else x = x % n + 1, y = y % n + 1;
		}
	}
	return 0;
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3584kb

input:

2
6
2
1
2
1
1
2
2
1
4
1
1
1
1
1
1
1
1

output:

? 1 4
? 2 4
? 1 5
? 2 4
? 3 4
? 1 3
? 1 4
! 2 4
? 1 3
? 2 3
? 1 4
? 4 3
? 1 3
? 1 2
? 1 3
! 1 3

result:

ok ok (2 test cases)

Test #2:

score: 0
Accepted
time: 13ms
memory: 3456kb

input:

1000
15
5
4
6
2
2
1
5
6
5
1
19
5
4
4
5
4
3
4
5
3
4
1
17
5
4
4
4
4
3
4
5
4
3
4
1
15
6
6
7
4
7
6
3
1
1
1
14
5
4
6
4
4
5
2
2
3
1
15
3
2
2
4
2
3
4
2
3
1
17
8
8
8
7
6
6
5
6
5
4
4
6
5
4
1
20
6
7
7
5
8
6
7
1
2
2
1
13
5
5
6
2
2
3
3
4
4
1
18
3
4
2
5
2
3
5
3
2
1
13
4
5
3
3
3
2
4
3
4
1
14
2
3
3
3
1
2
4
3
2
1
1...

output:

? 1 8
? 2 8
? 1 9
? 4 8
? 6 8
? 5 8
? 1 6
? 1 7
? 1 8
! 5 8
? 1 10
? 2 10
? 1 11
? 5 10
? 2 10
? 3 10
? 4 10
? 1 15
? 1 12
? 1 13
! 3 12
? 1 9
? 2 9
? 1 10
? 5 9
? 2 9
? 3 9
? 4 9
? 1 13
? 1 10
? 1 11
? 1 12
! 3 11
? 1 8
? 2 8
? 1 9
? 12 8
? 15 8
? 1 8
? 1 5
? 1 3
? 1 2
! 1 3
? 1 8
? 2 8
? 1 9
? 4 8...

result:

ok ok (1000 test cases)

Test #3:

score: 0
Accepted
time: 11ms
memory: 3456kb

input:

1000
21
3
4
4
6
3
3
2
5
3
3
2
1
22
8
7
7
6
6
7
3
3
4
1
20
5
4
6
2
3
2
1
7
6
5
1
22
10
9
9
5
3
4
4
6
8
7
7
1
21
9
8
8
4
2
3
3
6
7
8
1
21
8
9
7
5
6
5
4
6
6
5
1
24
11
11
11
5
3
4
4
6
9
8
8
1
22
10
10
9
6
9
10
9
5
2
1
2
1
21
4
3
3
5
4
4
3
5
2
3
1
23
8
9
7
2
3
3
9
7
8
1
21
10
10
10
9
8
8
4
3
3
4
5
7
7
1
...

output:

? 1 11
? 2 11
? 1 12
? 17 11
? 20 11
? 1 11
? 21 11
? 1 6
? 1 9
? 1 11
? 1 10
! 21 10
? 1 12
? 2 12
? 1 13
? 6 12
? 3 12
? 4 12
? 1 17
? 1 20
? 1 18
! 3 17
? 1 11
? 2 11
? 1 12
? 6 11
? 3 11
? 4 11
? 5 11
? 1 8
? 1 10
? 1 11
! 5 11
? 1 12
? 2 12
? 1 13
? 6 12
? 9 12
? 7 12
? 8 12
? 1 17
? 1 14
? 1 1...

result:

ok ok (1000 test cases)

Test #4:

score: 0
Accepted
time: 17ms
memory: 3584kb

input:

1000
25
8
9
9
7
10
8
9
2
3
1
2
1
25
6
7
7
7
6
6
5
4
4
2
3
1
25
11
11
12
7
9
9
8
5
3
4
4
1
25
5
4
6
6
3
5
4
6
3
5
4
1
26
12
12
11
7
10
8
8
7
5
5
1
26
11
12
12
7
9
9
10
5
3
3
4
1
26
13
13
11
12
10
5
1
1
2
11
12
11
1
27
12
11
13
6
3
5
5
9
8
8
1
25
9
10
10
3
3
1
2
6
10
9
10
1
27
9
8
10
7
7
7
6
4
5
6
5
1...

output:

? 1 13
? 2 13
? 1 14
? 20 13
? 24 13
? 1 13
? 25 13
? 1 7
? 1 4
? 1 6
? 1 5
! 1 6
? 1 13
? 2 13
? 1 14
? 20 13
? 24 13
? 1 13
? 25 13
? 1 7
? 1 11
? 1 9
? 1 8
! 25 9
? 1 13
? 2 13
? 1 14
? 20 13
? 24 13
? 22 13
? 23 13
? 1 7
? 1 4
? 1 6
? 1 5
! 23 6
? 1 13
? 2 13
? 1 14
? 7 13
? 3 13
? 5 13
? 4 13
?...

result:

ok ok (1000 test cases)

Test #5:

score: 0
Accepted
time: 11ms
memory: 3584kb

input:

1000
29
10
9
9
7
9
9
8
3
4
5
4
1
28
13
13
13
7
10
8
8
6
3
5
6
1
30
3
2
2
8
4
2
3
8
4
2
3
1
29
4
3
5
7
5
3
4
7
3
3
2
1
28
8
9
9
3
5
3
2
7
9
7
8
1
29
6
5
5
7
5
5
4
7
3
5
4
1
29
9
10
8
6
6
4
5
8
7
7
6
1
28
11
10
12
4
3
5
5
9
9
8
1
30
4
5
5
5
1
3
2
8
7
5
4
1
30
8
9
9
3
5
3
2
8
9
7
8
1
28
11
10
10
4
3
2
...

output:

? 1 15
? 2 15
? 1 16
? 8 15
? 4 15
? 2 15
? 3 15
? 1 22
? 1 26
? 1 24
? 1 23
! 3 22
? 1 15
? 2 15
? 1 16
? 22 15
? 26 15
? 24 15
? 23 15
? 1 8
? 1 4
? 1 6
? 1 7
! 24 8
? 1 16
? 2 16
? 1 17
? 8 16
? 4 16
? 2 16
? 3 16
? 1 23
? 1 19
? 1 17
? 1 18
! 2 17
? 1 15
? 2 15
? 1 16
? 8 15
? 4 15
? 2 15
? 3 15...

result:

ok ok (1000 test cases)

Test #6:

score: 0
Accepted
time: 19ms
memory: 3584kb

input:

1000
32
13
12
14
8
10
10
9
7
6
5
6
1
30
14
14
13
7
4
5
4
11
10
11
1
32
16
16
14
13
13
8
11
9
8
9
8
11
9
8
7
1
31
5
4
6
6
2
4
3
9
6
4
5
1
32
7
6
6
8
6
6
5
7
4
4
3
1
32
8
7
7
8
9
7
8
4
5
3
2
3
1
31
15
14
13
13
6
4
4
3
8
12
13
12
1
31
6
7
5
6
3
3
2
10
7
5
6
1
32
12
11
13
4
4
4
3
12
10
11
1
30
14
14
13
...

output:

? 1 17
? 2 17
? 1 18
? 9 17
? 4 17
? 6 17
? 5 17
? 1 11
? 1 7
? 1 9
? 1 8
! 5 9
? 1 16
? 2 16
? 1 17
? 23 1
? 27 1
? 25 1
? 26 1
? 16 28
? 16 26
? 16 27
! 26 28
? 1 17
? 2 18
? 3 19
? 4 19
? 3 20
? 11 19
? 6 19
? 8 19
? 9 19
? 10 19
? 3 27
? 3 22
? 3 24
? 3 25
? 3 26
! 9 26
? 1 16
? 2 16
? 1 17
? 8 ...

result:

ok ok (1000 test cases)

Test #7:

score: 0
Accepted
time: 16ms
memory: 3456kb

input:

1000
34
17
16
15
15
9
13
12
13
8
4
6
5
4
1
33
8
7
9
6
5
3
4
10
7
7
6
1
33
11
12
10
5
8
6
5
4
10
9
9
8
1
34
11
12
12
9
8
10
9
5
8
6
5
4
1
34
11
10
10
9
12
10
11
3
4
3
2
1
35
14
15
15
9
14
15
14
6
1
2
2
1
34
8
9
9
9
7
7
6
6
5
3
4
1
34
14
13
13
9
11
11
10
6
4
6
5
1
34
16
15
16
9
13
12
13
9
5
4
4
1
33
9...

output:

? 1 18
? 2 19
? 3 19
? 2 20
? 10 19
? 5 19
? 7 19
? 6 19
? 2 27
? 2 32
? 2 29
? 2 30
? 2 31
! 5 31
? 1 17
? 2 17
? 1 18
? 9 17
? 4 17
? 6 17
? 7 17
? 1 11
? 1 14
? 1 16
? 1 15
! 6 15
? 1 17
? 2 17
? 1 18
? 25 1
? 20 1
? 22 1
? 23 1
? 24 1
? 17 29
? 17 32
? 17 30
? 17 31
! 24 31
? 1 18
? 2 18
? 1 19
...

result:

ok ok (1000 test cases)

Test #8:

score: 0
Accepted
time: 16ms
memory: 3584kb

input:

1000
36
18
17
16
17
8
3
1
1
17
17
1
36
3
4
4
8
3
2
1
2
9
7
4
3
1
36
13
12
14
9
11
12
11
10
5
6
5
4
1
36
5
4
6
9
5
4
3
4
9
5
3
4
1
36
18
17
16
16
9
13
12
13
8
4
6
5
5
1
36
12
11
11
3
4
5
4
9
12
11
10
11
1
35
13
14
12
9
9
11
10
6
7
6
5
1
36
13
12
12
4
4
4
3
9
13
12
11
12
1
36
14
13
13
9
10
10
9
7
10
8...

output:

? 1 19
? 2 20
? 3 20
? 2 21
? 11 20
? 16 20
? 18 20
? 19 20
? 2 19
? 2 20
! 18 20
? 1 19
? 2 19
? 1 20
? 28 19
? 33 19
? 36 19
? 35 19
? 34 19
? 1 10
? 1 15
? 1 18
? 1 19
! 35 19
? 1 19
? 2 19
? 1 20
? 10 19
? 5 19
? 2 19
? 3 19
? 4 19
? 1 11
? 1 7
? 1 9
? 1 10
! 4 10
? 1 19
? 2 19
? 1 20
? 10 19
? ...

result:

ok ok (1000 test cases)

Test #9:

score: 0
Accepted
time: 25ms
memory: 3456kb

input:

1000
37
17
17
18
8
5
6
7
9
13
12
12
1
36
17
17
16
9
13
11
10
10
11
8
7
8
1
38
9
8
10
6
5
3
4
12
8
8
7
1
37
15
14
14
6
4
4
3
4
10
15
14
13
14
1
37
12
13
13
3
4
1
2
9
14
13
12
1
36
8
9
7
9
4
6
5
9
5
7
6
1
37
6
7
5
9
4
5
4
3
10
6
4
5
1
37
18
18
18
18
17
16
16
9
13
11
10
10
8
5
8
9
1
37
17
17
18
8
3
2
2...

output:

? 1 19
? 2 19
? 1 20
? 29 19
? 24 19
? 27 19
? 26 19
? 1 10
? 1 15
? 1 13
? 1 14
! 27 14
? 1 19
? 2 19
? 1 20
? 28 1
? 23 1
? 25 1
? 26 1
? 27 1
? 19 31
? 19 28
? 19 26
? 19 27
! 26 28
? 1 20
? 2 20
? 1 21
? 10 20
? 5 20
? 7 20
? 8 20
? 1 13
? 1 17
? 1 19
? 1 18
! 7 18
? 1 19
? 2 19
? 1 20
? 10 19
?...

result:

ok ok (1000 test cases)

Test #10:

score: 0
Accepted
time: 22ms
memory: 3584kb

input:

1000
39
18
17
17
9
5
7
6
6
10
14
13
13
14
1
38
8
9
7
10
10
7
8
5
4
3
2
1
38
19
19
17
16
16
8
5
6
5
6
10
13
13
14
1
39
12
11
13
10
14
11
12
3
5
4
3
2
1
38
15
16
14
10
15
14
15
6
3
3
2
1
39
4
5
3
8
2
3
2
1
11
8
6
5
4
1
39
18
18
19
10
16
17
16
17
9
4
2
3
3
1
38
18
17
18
9
4
1
1
18
18
1
39
14
15
13
4
3
...

output:

? 1 20
? 2 20
? 1 21
? 10 20
? 15 20
? 12 20
? 13 20
? 14 20
? 1 30
? 1 24
? 1 27
? 1 25
? 1 26
! 13 25
? 1 20
? 2 20
? 1 21
? 29 1
? 24 1
? 21 1
? 22 1
? 20 30
? 20 35
? 20 32
? 20 33
! 21 33
? 1 20
? 2 21
? 3 22
? 4 22
? 3 23
? 12 22
? 17 22
? 14 22
? 15 22
? 16 22
? 3 31
? 3 26
? 3 28
? 3 27
! 15...

result:

ok ok (1000 test cases)

Test #11:

score: 0
Accepted
time: 15ms
memory: 3584kb

input:

1000
40
12
11
11
10
8
7
7
6
10
8
9
7
8
1
40
18
17
17
8
5
8
7
10
14
13
13
12
1
40
15
14
14
10
15
14
13
14
5
5
3
4
1
40
8
9
9
10
12
9
8
4
4
1
2
1
40
16
17
15
10
16
15
14
15
7
4
4
3
1
40
15
16
16
9
11
8
7
8
10
11
10
10
9
1
41
13
14
14
11
17
14
13
3
4
1
2
1
40
7
8
6
10
5
6
5
4
10
5
5
4
1
40
18
19
17
10
...

output:

? 1 21
? 2 21
? 1 22
? 11 21
? 5 21
? 8 21
? 6 21
? 7 21
? 1 31
? 1 25
? 1 28
? 1 26
? 1 27
! 7 26
? 1 21
? 2 21
? 1 22
? 11 21
? 16 21
? 13 21
? 12 21
? 1 31
? 1 25
? 1 28
? 1 26
? 1 27
! 12 27
? 1 21
? 2 21
? 1 22
? 11 21
? 5 21
? 2 21
? 3 21
? 4 21
? 1 31
? 1 36
? 1 33
? 1 34
! 3 33
? 1 21
? 2 21...

result:

ok ok (1000 test cases)

Test #12:

score: 0
Accepted
time: 16ms
memory: 3456kb

input:

1000
42
11
10
12
11
7
8
6
7
9
7
7
6
1
41
17
18
16
7
5
6
6
5
14
15
13
1
41
8
9
9
11
8
7
6
7
8
4
5
3
4
1
41
12
13
13
10
8
7
7
6
10
8
9
7
8
1
41
12
11
11
4
8
5
4
3
11
12
11
10
11
1
41
18
19
19
11
14
14
13
14
8
5
6
7
1
41
14
15
13
4
5
3
3
2
16
14
13
1
41
20
20
19
18
18
10
15
12
11
10
11
15
12
11
10
1
41...

output:

? 1 22
? 2 22
? 1 23
? 11 22
? 5 22
? 8 22
? 6 22
? 7 22
? 1 14
? 1 18
? 1 16
? 1 17
! 6 17
? 1 21
? 2 21
? 1 22
? 31 1
? 37 1
? 34 1
? 32 1
? 33 1
? 21 37
? 21 40
? 21 38
! 33 38
? 1 21
? 2 21
? 1 22
? 32 21
? 38 21
? 41 21
? 40 21
? 39 21
? 1 11
? 1 17
? 1 14
? 1 16
? 1 15
! 40 16
? 1 21
? 2 21
? ...

result:

ok ok (1000 test cases)

Test #13:

score: 0
Accepted
time: 25ms
memory: 3584kb

input:

1000
43
4
3
5
10
4
3
2
3
11
7
4
3
1
42
18
17
19
8
4
5
4
3
17
17
16
1
43
6
5
7
8
2
5
3
12
8
6
5
1
43
18
19
19
11
13
10
9
10
11
14
11
10
11
1
43
21
21
21
20
19
19
11
17
18
17
18
10
4
2
4
1
43
17
18
18
11
12
14
13
7
5
8
6
7
1
43
18
17
19
11
17
17
16
17
8
3
3
4
4
1
43
21
21
21
20
21
19
10
4
1
1
20
20
1
...

output:

? 1 22
? 2 22
? 1 23
? 11 22
? 5 22
? 2 22
? 3 22
? 4 22
? 1 12
? 1 17
? 1 20
? 1 21
! 3 21
? 1 22
? 2 22
? 1 23
? 11 22
? 17 22
? 14 22
? 15 22
? 16 22
? 1 19
? 1 21
? 1 20
! 16 20
? 1 22
? 2 22
? 1 23
? 11 22
? 5 22
? 8 22
? 6 22
? 1 13
? 1 18
? 1 20
? 1 21
! 5 21
? 1 22
? 2 22
? 1 23
? 33 22
? 39...

result:

ok ok (1000 test cases)

Test #14:

score: 0
Accepted
time: 19ms
memory: 3584kb

input:

1000
44
22
22
20
19
19
11
17
18
17
18
9
5
6
5
4
1
44
11
10
10
11
8
9
8
7
10
6
7
5
6
1
43
11
12
10
11
12
9
10
5
6
3
4
1
43
21
21
21
21
20
19
19
10
5
7
6
5
11
17
18
17
16
1
44
19
18
18
11
17
19
19
18
8
2
2
3
1
44
16
15
17
11
13
14
13
12
7
8
6
5
1
44
17
18
18
6
5
3
4
11
17
15
16
1
44
10
9
9
7
5
4
4
3
1...

output:

? 1 23
? 2 24
? 3 25
? 4 25
? 3 26
? 14 25
? 8 25
? 5 25
? 6 25
? 7 25
? 3 36
? 3 42
? 3 39
? 3 40
? 3 41
! 6 41
? 1 23
? 2 23
? 1 24
? 12 23
? 6 23
? 3 23
? 4 23
? 5 23
? 1 34
? 1 28
? 1 31
? 1 29
? 1 30
! 5 29
? 1 22
? 2 22
? 1 23
? 33 1
? 27 1
? 24 1
? 25 1
? 22 34
? 22 39
? 22 36
? 22 35
! 24 36...

result:

ok ok (1000 test cases)

Test #15:

score: 0
Accepted
time: 21ms
memory: 3456kb

input:

1000
45
20
21
21
12
18
20
20
19
9
3
2
2
3
1
45
16
17
17
12
13
14
13
12
5
5
8
6
1
45
10
9
11
11
7
8
7
6
9
6
7
6
5
1
45
15
14
14
11
10
13
11
8
10
7
6
7
1
45
11
10
12
11
14
11
11
10
4
6
3
3
2
1
45
16
17
17
11
11
8
9
11
11
10
10
9
1
45
19
20
18
12
18
17
16
17
9
5
6
4
1
45
5
6
6
10
4
3
2
3
11
8
5
5
4
1
4...

output:

? 1 23
? 2 23
? 1 24
? 35 23
? 41 23
? 44 23
? 1 23
? 45 23
? 1 12
? 1 6
? 1 3
? 1 5
? 1 4
! 45 5
? 1 23
? 2 23
? 1 24
? 35 23
? 41 23
? 44 23
? 43 23
? 42 23
? 1 12
? 1 6
? 1 9
? 1 11
! 42 12
? 1 23
? 2 23
? 1 24
? 12 23
? 6 23
? 3 23
? 4 23
? 5 23
? 1 14
? 1 19
? 1 16
? 1 17
? 1 18
! 5 18
? 1 23
?...

result:

ok ok (1000 test cases)

Test #16:

score: 0
Accepted
time: 24ms
memory: 3456kb

input:

1000
46
18
17
17
9
13
10
9
8
12
13
12
12
11
1
46
9
8
8
12
8
7
6
7
10
4
7
5
1
46
22
21
21
12
17
15
16
16
11
6
8
7
7
1
46
19
18
20
12
14
15
15
10
7
7
6
1
46
5
6
6
12
10
7
5
6
8
2
3
2
1
1
46
21
20
20
10
6
9
9
8
12
16
15
15
14
1
46
18
17
17
7
6
9
8
12
13
14
12
13
1
46
16
15
15
5
6
8
6
12
13
14
13
12
1
4...

output:

? 1 24
? 2 24
? 1 25
? 12 24
? 6 24
? 9 24
? 10 24
? 11 24
? 1 35
? 1 29
? 1 32
? 1 30
? 1 31
! 11 31
? 1 24
? 2 24
? 1 25
? 12 24
? 6 24
? 3 24
? 4 24
? 5 24
? 1 35
? 1 29
? 1 32
? 1 30
! 4 29
? 1 24
? 2 24
? 1 25
? 12 24
? 6 24
? 9 24
? 7 24
? 8 24
? 1 35
? 1 41
? 1 38
? 1 39
? 1 40
! 7 39
? 1 24
...

result:

ok ok (1000 test cases)

Test #17:

score: -100
Wrong Answer
time: 1ms
memory: 3584kb

input:

1000
1000000000
499999999
499999999
499999998
249999999
125000000
187499999
156249999
140624999
132812499
128906249
126953125
127929688
128417968
128173828
128051758
127990723
127960205
127944947
127952577
127956391
127954484
127953530
127953053
127952815
127952696
127952636
127952607
127952621
1279...

output:

? 1 500000001
? 2 500000001
? 1 500000002
? 750000001 1
? 875000001 1
? 812500001 1
? 843750001 1
? 859375001 1
? 867187501 1
? 871093751 1
? 873046876 1
? 872070313 1
? 871582032 1
? 871826172 1
? 871948242 1
? 872009277 1
? 872039795 1
? 872055054 1
? 872047424 1
? 872043609 1
? 872045516 1
? 8720...

result:

wrong answer Too many queries: 41 (test case 1)
English 繁體中文 简体中文

服务器时间: 2025-02-08 23:00:24 | 开源项目