QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#553775#8939. Permutationucup-team191#WA 75ms1640kbC++231.0kb2024-09-08 20:08:122024-09-08 20:08:13

Judging History

This is the latest submission verdict.

  • [2024-09-08 20:08:13]
  • Judged
  • Verdict: WA
  • Time: 75ms
  • Memory: 1640kb
Show
  • [2024-09-08 20:08:12]
  • Submitted

answer

#include <cstdio>

int ask(int l, int r) {
	printf("? %d %d\n", l, r);
	fflush(stdout);
	int x; scanf("%d", &x);
	return x;
}

int solve(int l, int r, int x = -1) {
	if(x == -1 && l != r) x = ask(l, r);
	if(l == r) return l;
	if(l == r - 1) return l + r - x;
	if(l == r - 2) {
		if(x == l) return solve(l + 1, r);
		if(x == r) return solve(l, r - 1);
		return (ask(l, x) == x) ? l : r;
	}
	int mid = (l + r) / 2;
	if(x > mid && (r - l + 1) % 2 == 1) mid--;
	if(x <= mid) {
		int x_l = ask(l, mid);
		if(x_l == x) return solve(l, mid, x);
		int mid2 = (r + mid + 1) / 2;
		if((r - mid) % 2 == 1) mid2--;
		if(ask(x, mid2) == x) return solve(mid + 1, mid2);
		else return solve(mid2 + 1, r);
	} else {
		int x_r = ask(mid + 1, r);
		if(x_r == x) return solve(mid + 1, r, x);
		int mid2 = (l + mid) / 2;
		if(ask(mid2 + 1, x) == x) return solve(mid2 + 1, mid);
		else return solve(l, mid2);
	}
}

int main() {
	int T; scanf("%d", &T);
	for(;T--;) {
		int n; scanf("%d", &n);
		printf("! %d\n", solve(1, n));
		fflush(stdout);
	}
}
Source code, Language: C++23

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 1580kb

input:

3
5
3
2
3
6
6
5
3
1
4
3
3

output:

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

result:

ok Correct (3 test cases)

Test #2:

score: 0
Accepted
time: 35ms
memory: 1588kb

input:

10000
10
2
2
3
2
10
10
10
8
7
10
5
1
5
6
10
4
4
4
4
10
10
6
6
3
2
10
3
3
3
2
10
1
5
5
9
9
10
1
3
1
6
10
2
4
4
9
8
10
3
3
1
3
10
4
1
7
8
9
10
8
7
7
1
2
10
4
1
5
9
8
10
7
8
7
4
10
5
1
7
8
10
10
8
8
6
9
10
2
1
2
7
10
6
6
8
6
10
1
3
1
6
10
7
9
5
1
2
10
7
8
4
1
2
10
3
4
4
10
8
10
4
4
4
3
10
8
7
7
2
2
10
...

output:

? 1 10
? 1 5
? 1 3
? 2 4
! 4
? 1 10
? 6 10
? 8 10
? 7 10
! 6
? 1 10
? 1 5
? 5 7
? 6 7
! 7
? 1 10
? 1 5
? 3 5
? 3 4
! 3
? 1 10
? 6 10
? 4 10
? 1 3
? 1 2
! 1
? 1 10
? 1 5
? 1 3
? 1 2
! 1
? 1 10
? 1 5
? 1 7
? 8 10
? 8 9
! 8
? 1 10
? 1 5
? 1 7
? 6 7
! 7
? 1 10
? 1 5
? 2 7
? 8 10
? 8 9
! 10
? 1 10
? 1 5
...

result:

ok Correct (10000 test cases)

Test #3:

score: 0
Accepted
time: 50ms
memory: 1632kb

input:

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

output:

? 1 3
? 2 3
! 3
? 1 11
? 1 6
? 4 6
? 4 5
! 6
? 1 2
! 1
? 1 19
? 1 10
? 1 5
? 3 7
? 8 10
? 9 10
! 10
? 1 7
? 4 7
? 3 5
! 3
? 1 3
? 1 2
! 2
? 1 19
? 1 10
? 6 10
? 4 6
? 1 3
? 2 3
! 3
? 1 2
! 1
? 1 15
? 8 15
? 8 11
? 10 11
? 9 11
! 9
? 1 14
? 1 7
? 1 4
? 1 2
? 1 3
! 4
? 1 16
? 1 8
? 1 4
? 4 6
? 5 6
! 6...

result:

ok Correct (10000 test cases)

Test #4:

score: 0
Accepted
time: 71ms
memory: 1624kb

input:

10000
47
23
23
24
11
2
1
2
14
8
8
8
9
8
25
6
13
6
18
17
17
15
7
4
2
4
9
2
2
2
2
27
27
27
27
24
24
21
21
7
7
6
7
5
43
41
37
21
7
8
5
3
1
22
6
4
14
20
20
21
34
29
25
29
17
17
16
17
42
20
20
20
20
19
20
47
21
21
21
19
21
16
17
41
25
25
30
30
39
39
38
19
17
17
16
16
12
10
21
14
14
14
15
13
11
27
2
1
2
1...

output:

? 1 47
? 1 24
? 13 24
? 7 23
? 1 6
? 1 3
? 2 4
! 4
? 1 14
? 8 14
? 8 11
? 8 9
? 8 10
! 10
? 1 25
? 1 13
? 6 19
? 14 19
? 17 19
? 16 18
? 14 15
! 14
? 1 7
? 1 4
? 4 5
! 5
? 1 9
? 1 5
? 1 3
? 1 2
! 1
? 1 27
? 14 27
? 21 27
? 24 27
? 23 27
? 21 22
! 22
? 1 21
? 1 11
? 6 11
? 4 7
? 4 5
! 4
? 1 43
? 22 4...

result:

ok Correct (10000 test cases)

Test #5:

score: 0
Accepted
time: 75ms
memory: 1640kb

input:

10000
100
47
5
47
61
53
68
71
71
71
9
2
2
2
1
53
46
35
14
6
6
6
7
6
33
3
16
16
31
31
30
32
82
60
42
60
29
29
28
29
26
88
39
8
39
59
59
59
61
59
71
24
29
29
59
59
59
60
60
92
52
52
56
70
88
88
89
88
24
11
11
9
11
5
5
66
51
51
66
45
39
39
38
40
92
43
43
38
43
20
20
20
19
48
1
1
1
5
1
9
7
85
28
28
28
2...

output:

? 1 100
? 1 50
? 47 75
? 51 75
? 51 63
? 61 69
? 70 75
? 70 72
? 70 71
! 70
? 1 9
? 1 5
? 1 3
? 1 2
! 3
? 1 53
? 27 53
? 14 46
? 1 13
? 1 7
? 4 7
? 6 7
? 5 6
! 5
? 1 33
? 1 17
? 3 25
? 26 33
? 30 33
? 30 31
? 31 32
! 33
? 1 82
? 42 82
? 22 60
? 22 41
? 22 31
? 27 31
? 25 29
? 25 26
! 25
? 1 88
? 1 4...

result:

ok Correct (10000 test cases)

Test #6:

score: 0
Accepted
time: 67ms
memory: 1536kb

input:

10000
50
10
10
10
7
10
6
5
50
11
11
9
18
23
23
25
50
44
40
44
20
20
21
21
25
50
24
14
29
45
45
45
44
46
50
50
50
50
50
49
50
50
36
39
23
12
12
11
12
50
29
36
20
13
12
13
6
5
50
30
42
22
1
1
1
2
1
50
25
15
25
30
30
31
30
50
18
20
20
49
47
47
39
39
50
9
9
9
9
7
11
13
50
26
43
26
17
17
19
16
15
50
16
1...

output:

? 1 50
? 1 25
? 1 13
? 7 13
? 4 10
? 4 6
? 4 5
! 4
? 1 50
? 1 25
? 1 13
? 11 19
? 20 25
? 23 25
? 24 25
! 24
? 1 50
? 26 50
? 14 44
? 14 25
? 20 25
? 20 22
? 20 23
? 24 25
! 24
? 1 50
? 1 25
? 24 37
? 38 50
? 44 50
? 44 47
? 44 45
? 45 46
! 47
? 1 50
? 26 50
? 38 50
? 44 50
? 47 50
? 46 50
! 46
? 1 ...

result:

ok Correct (10000 test cases)

Test #7:

score: 0
Accepted
time: 72ms
memory: 1624kb

input:

10000
100
76
78
35
5
5
3
5
9
8
100
29
29
50
29
20
20
22
22
24
100
64
64
69
64
86
86
87
84
83
100
51
51
57
51
79
81
79
84
83
100
44
44
50
42
13
13
12
12
7
100
64
92
64
41
41
41
41
40
40
100
93
56
93
40
40
44
40
45
47
100
37
2
37
57
54
57
68
68
67
100
76
76
76
76
80
76
85
83
100
32
32
32
31
44
49
48
4...

output:

? 1 100
? 51 100
? 26 76
? 1 25
? 1 13
? 1 7
? 5 10
? 8 10
? 8 9
! 10
? 1 100
? 1 50
? 26 50
? 14 29
? 14 25
? 20 25
? 20 22
? 20 23
? 24 25
! 25
? 1 100
? 51 100
? 51 75
? 64 87
? 76 87
? 82 87
? 85 87
? 84 86
? 82 83
! 82
? 1 100
? 51 100
? 51 75
? 51 87
? 76 87
? 76 81
? 79 84
? 82 84
? 82 83
! 8...

result:

ok Correct (10000 test cases)

Test #8:

score: 0
Accepted
time: 8ms
memory: 1632kb

input:

1000
1000
475
426
728
896
974
896
867
867
860
858
847
847
848
847
1000
278
17
278
598
534
598
679
665
679
652
655
647
645
645
1000
75
128
75
607
604
644
713
695
732
749
745
749
742
741
742
1000
239
239
45
350
432
429
432
442
451
458
462
462
463
462
1000
978
978
978
978
997
978
914
920
914
923
923
92...

output:

? 1 1000
? 1 500
? 475 750
? 751 1000
? 876 1000
? 814 896
? 814 875
? 845 875
? 860 875
? 853 867
? 845 852
? 845 848
? 847 848
? 846 847
! 846
? 1 1000
? 1 500
? 278 750
? 501 750
? 501 625
? 598 687
? 626 687
? 657 687
? 642 679
? 642 656
? 649 656
? 646 652
? 642 645
? 644 645
! 644
? 1 1000
? 1...

result:

ok Correct (1000 test cases)

Test #9:

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

input:

1017
272
246
186
246
111
110
110
73
73
71
73
75
114
105
91
91
2
2
2
2
2
910
173
173
173
127
127
14
29
29
56
51
56
48
50
726
229
229
201
201
63
71
63
28
28
28
29
27
24
861
315
104
315
491
528
551
632
641
614
593
593
593
594
593
1984
133
133
406
133
571
512
571
673
682
673
650
650
650
651
649
1145
988...

output:

? 1 272
? 137 272
? 69 246
? 69 136
? 103 136
? 86 111
? 69 85
? 69 77
? 69 73
? 73 75
? 74 75
! 74
? 1 114
? 58 114
? 30 105
? 1 29
? 1 15
? 1 8
? 1 4
? 1 2
! 1
? 1 910
? 1 455
? 1 228
? 115 228
? 58 173
? 1 57
? 1 29
? 14 43
? 44 57
? 51 57
? 48 56
? 48 50
? 49 50
! 49
? 1 726
? 1 363
? 182 363
? ...

result:

ok Correct (1017 test cases)

Test #10:

score: 0
Accepted
time: 2ms
memory: 1536kb

input:

10
100000
3893
3893
3505
30673
43582
43582
43582
43582
43582
43470
43582
43242
43197
43242
43289
43298
43279
43268
43263
43268
43270
43269
100000
32066
19090
54928
88585
88585
88585
89959
88585
91599
91474
91599
91257
91257
91225
91257
91325
91312
91339
91348
91349
91348
91354
91353
100000
50288
867...

output:

? 1 100000
? 1 50000
? 1 25000
? 3893 37500
? 37501 50000
? 37501 43750
? 40626 43750
? 42188 43750
? 42969 43750
? 43360 43750
? 43165 43582
? 43165 43359
? 43165 43262
? 43242 43310
? 43263 43310
? 43287 43310
? 43275 43289
? 43263 43274
? 43263 43268
? 43268 43271
? 43269 43271
? 43269 43270
! 43...

result:

ok Correct (10 test cases)

Test #11:

score: 0
Accepted
time: 3ms
memory: 1536kb

input:

21
84335
47947
60969
22445
9296
1509
11772
20931
19830
20931
17510
17510
17606
17510
17352
17352
17346
17352
17320
17320
17320
17318
17321
159962
128177
145530
128177
54814
54814
59035
49869
40850
42103
40850
43214
43214
43231
43550
43675
43675
43675
43670
43689
43695
43695
43696
43695
19298
18479
1...

output:

? 1 84335
? 42168 84335
? 21085 47947
? 1 21084
? 1 10542
? 9296 15813
? 15814 21084
? 18449 21084
? 17132 20931
? 17132 18448
? 17132 17790
? 17461 17790
? 17297 17510
? 17297 17460
? 17297 17378
? 17338 17378
? 17318 17352
? 17318 17337
? 17318 17327
? 17318 17322
? 17318 17320
? 17320 17321
! 173...

result:

ok Correct (21 test cases)

Test #12:

score: 0
Accepted
time: 0ms
memory: 1632kb

input:

1
1000000
641602
641602
561698
641602
783270
783270
783270
783270
786055
786055
794273
794682
794682
796734
796734
796734
796686
796788
796850
796850
796851
796850
796864
796864
796863
796864

output:

? 1 1000000
? 500001 1000000
? 500001 750000
? 641602 875000
? 750001 875000
? 750001 812500
? 781251 812500
? 781251 796875
? 781251 789063
? 783270 792969
? 792970 796875
? 792970 794922
? 794273 795898
? 795899 796875
? 796387 796875
? 796631 796875
? 796631 796753
? 796734 796814
? 796815 796875...

result:

ok Correct (1 test case)

Test #13:

score: 0
Accepted
time: 3ms
memory: 1604kb

input:

16
232936
229707
229707
229707
229707
229707
231039
229707
223556
223533
224031
225261
225261
225261
225290
225290
225375
225395
225407
225417
225419
225417
225425
225423
8676
6498
6498
6498
5867
4978
4731
4731
4731
4731
4717
4717
4684
4681
4690
4692
4691
4693
221085
172303
209705
142841
20545
20545...

output:

? 1 232936
? 116469 232936
? 174703 232936
? 203820 232936
? 218378 232936
? 225657 232936
? 222018 229707
? 222018 225656
? 222018 223837
? 223556 224746
? 224747 225656
? 225202 225656
? 225202 225429
? 225202 225315
? 225261 225372
? 225373 225429
? 225373 225401
? 225375 225415
? 225416 225429
?...

result:

ok Correct (16 test cases)

Test #14:

score: -100
Wrong Answer
time: 25ms
memory: 1536kb

input:

1994
667
666
667
665
167
166
166
42
41
41
11
10
10
3
2
374
373
374
372
94
93
93
24
23
23
6
5
5
2
488
486
488
485
122
121
121
31
30
30
8
7
7
2
922
921
922
920
231
230
230
58
57
57
15
14
14
4
3
3
639
637
639
636
160
159
159
40
39
39
10
9
9
3
2
353
350
353
349
88
87
87
22
21
21
6
5
5
2
71
66
71
65
18
1...

output:

? 1 667
? 334 667
? 168 666
? 1 167
? 84 167
? 43 167
? 1 42
? 22 42
? 12 42
? 1 11
? 6 11
? 4 11
? 1 3
? 1 2
! 1
? 1 374
? 188 374
? 95 373
? 1 94
? 48 94
? 25 94
? 1 24
? 13 24
? 7 24
? 1 6
? 4 6
? 3 6
? 1 2
! 1
? 1 488
? 245 488
? 123 486
? 1 122
? 62 122
? 32 122
? 1 31
? 16 31
? 9 31
? 1 8
? 5 ...

result:

wrong answer Too long queries, n = 938, now length 2815 (test case 186)
English 繁體中文 简体中文

Server Time: 2025-02-10 22:56:11 | OpenSource Project