QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#138374#6394. Turn on the LightSchi2oidWA 6ms13488kbC++141.0kb2023-08-11 16:49:462023-08-11 16:49:49

Judging History

你现在查看的是最新测评结果

  • [2023-08-11 16:49:49]
  • 评测
  • 测评结果：WA
  • 用时：6ms
  • 内存：13488kb
查看
  • [2023-08-11 16:49:46]
  • 提交

answer

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

int ask(int x) {
	int ret;
	cout << "? " << x << endl;
	cin >> ret;
	return ret;
	}
int id[2][2000005];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		id[0][i] = i;
	bool op = 0;
	int bef = 0;
	while (n >= 4) {
		int p1 = n / 4, p2 = n - n / 4;
		int x = ask(id[op][p1]);
		if (x == bef) {
			cout << "! " << p1;
			return 0;
			}
		int y = ask(id[op][p2]);
		if (y == x) {
			cout << "! " << p2;
			return 0;
			}
		int delta = y - bef;
		op ^= 1;
		if (delta == 0) {
			int cnt = 0;
			for (int i = p1 + 1; i < p2; i++) {
				id[op][++cnt] = id[op ^ 1][i];
				}
			n = cnt;
			}
		else {
			int cnt = 0;
			for (int i = 1; i < p1; i++) {
				id[op][++cnt] = id[op ^ 1][i];
				}
			for (int i = p2 + 1; i <= n; i++) {
				id[op][++cnt] = id[op ^ 1][i];
				}
			n = cnt;
			}
		bef = y;
		}
	for (int i = 1; i <= n; i++) {
		int x = ask(id[op][i]);
		if (x == bef) {
			cout << "! " << id[op][i];
			return 0;
			}
		bef = x;
		}
	return 0;
	}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3412kb

input:

3
1
2
2

output:

? 1
? 2
? 3
! 3

result:

ok Correct position at 3

Test #2:

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

input:

10
1
0
1
0
1
1

output:

? 2
? 8
? 3
? 6
? 4
? 5
! 5

result:

ok Correct position at 5

Test #3:

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

input:

9
1
0
1
0
0

output:

? 2
? 7
? 3
? 5
? 4
! 4

result:

ok Correct position at 4

Test #4:

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

input:

8
1
0
1
1

output:

? 2
? 6
? 3
? 4
! 4

result:

ok Correct position at 4

Test #5:

score: 0
Accepted
time: 1ms
memory: 5516kb

input:

7
1
0
1
0
0

output:

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

result:

ok Correct position at 3

Test #6:

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

input:

6
1
0
1
1

output:

? 1
? 5
? 2
? 3
! 3

result:

ok Correct position at 3

Test #7:

score: 0
Accepted
time: 1ms
memory: 5676kb

input:

5
1
0
1
1

output:

? 1
? 4
? 2
? 3
! 3

result:

ok Correct position at 3

Test #8:

score: 0
Accepted
time: 1ms
memory: 3416kb

input:

4
1
1

output:

? 1
? 3
! 3

result:

ok Correct position at 3

Test #9:

score: 0
Accepted
time: 1ms
memory: 3448kb

input:

3
1
1

output:

? 1
? 2
! 2

result:

ok Correct position at 2

Test #10:

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

input:

2
1
1

output:

? 1
? 2
! 2

result:

ok Correct position at 2

Test #11:

score: 0
Accepted
time: 1ms
memory: 3452kb

input:

1
0

output:

? 1
! 1

result:

ok Correct position at 1

Test #12:

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

input:

1000000
1
0
1
0
1
0
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
24
25
24
25
26
26

output:

? 250000
? 750000
? 374999
? 625000
? 437499
? 562499
? 468748
? 531249
? 484373
? 515623
? 476560
? 523436
? 472653
? 527343
? 470700
? 529296
? 469723
? 530273
? 469235
? 530761
? 468991
? 531005
? 468869
? 531127
? 468808
? 531188
? 468777
? 531219
? 468762
? 531234
? 468754
? 531242
? 468750
? 5...

result:

ok Correct position at 531243

Test #13:

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

input:

999999
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
18
19
18
19
20
20

output:

? 249999
? 750000
? 374999
? 624999
? 437498
? 562499
? 468748
? 531248
? 484372
? 515623
? 492184
? 507810
? 496090
? 503903
? 498043
? 501949
? 497066
? 502926
? 496577
? 503415
? 496333
? 503659
? 496211
? 503781
? 496150
? 503842
? 496119
? 503873
? 496104
? 503888
? 496096
? 503896
? 496092
? 5...

result:

ok Correct position at 503897

Test #14:

score: 0
Accepted
time: 1ms
memory: 13488kb

input:

999998
1
0
1
0
1
0
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
24
25
24
25
26
26

output:

? 249999
? 749999
? 374998
? 624999
? 437498
? 562498
? 468747
? 531248
? 484372
? 515622
? 476559
? 523435
? 472652
? 527342
? 470699
? 529295
? 469722
? 530272
? 469234
? 530760
? 468990
? 531004
? 468868
? 531126
? 468807
? 531187
? 468776
? 531218
? 468761
? 531233
? 468753
? 531241
? 468749
? 5...

result:

ok Correct position at 531242

Test #15:

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

input:

999997
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
18
19
18
19
20
20

output:

? 249999
? 749998
? 374998
? 624998
? 437497
? 562498
? 468747
? 531247
? 484371
? 515622
? 492183
? 507809
? 496089
? 503902
? 498042
? 501948
? 497065
? 502925
? 496576
? 503414
? 496332
? 503658
? 496210
? 503780
? 496149
? 503841
? 496118
? 503872
? 496103
? 503887
? 496095
? 503895
? 496091
? 5...

result:

ok Correct position at 503896

Test #16:

score: 0
Accepted
time: 6ms
memory: 11692kb

input:

999996
1
0
1
0
1
0
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
24
25
24
25
26
26

output:

? 249999
? 749997
? 374998
? 624997
? 437497
? 562497
? 468746
? 531247
? 484371
? 515621
? 476558
? 523434
? 472651
? 527341
? 470698
? 529294
? 469721
? 530271
? 469233
? 530759
? 468989
? 531003
? 468867
? 531125
? 468806
? 531186
? 468775
? 531217
? 468760
? 531232
? 468752
? 531240
? 468748
? 5...

result:

ok Correct position at 531241

Test #17:

score: 0
Accepted
time: 1ms
memory: 12968kb

input:

999995
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
18
19
18
19
20
20

output:

? 249998
? 749997
? 374997
? 624997
? 437496
? 562497
? 468746
? 531246
? 484370
? 515621
? 492182
? 507808
? 496088
? 503901
? 498041
? 501947
? 497064
? 502924
? 496575
? 503413
? 496331
? 503657
? 496209
? 503779
? 496148
? 503840
? 496117
? 503871
? 496102
? 503886
? 496094
? 503894
? 496090
? 5...

result:

ok Correct position at 503895

Test #18:

score: 0
Accepted
time: 6ms
memory: 12560kb

input:

999994
1
0
1
0
1
0
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
24
25
24
25
26
26

output:

? 249998
? 749996
? 374997
? 624996
? 437496
? 562496
? 468745
? 531246
? 484370
? 515620
? 476557
? 523433
? 472650
? 527340
? 470697
? 529293
? 469720
? 530270
? 469232
? 530758
? 468988
? 531002
? 468866
? 531124
? 468805
? 531185
? 468774
? 531216
? 468759
? 531231
? 468751
? 531239
? 468747
? 5...

result:

ok Correct position at 531240

Test #19:

score: 0
Accepted
time: 4ms
memory: 12056kb

input:

999993
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
18
19
18
19
20
20

output:

? 249998
? 749995
? 374997
? 624995
? 437496
? 562495
? 468745
? 531245
? 484369
? 515620
? 492181
? 507807
? 496087
? 503900
? 498040
? 501946
? 497063
? 502923
? 496574
? 503412
? 496330
? 503656
? 496208
? 503778
? 496147
? 503839
? 496116
? 503870
? 496101
? 503885
? 496093
? 503893
? 496089
? 5...

result:

ok Correct position at 503894

Test #20:

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

input:

999992
1
0
1
0
1
0
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
24
25
24
25
26
26

output:

? 249998
? 749994
? 374996
? 624995
? 437495
? 562495
? 468744
? 531245
? 484369
? 515619
? 476556
? 523432
? 472649
? 527339
? 470696
? 529292
? 469719
? 530269
? 469231
? 530757
? 468987
? 531001
? 468865
? 531123
? 468804
? 531184
? 468773
? 531215
? 468758
? 531230
? 468750
? 531238
? 468746
? 5...

result:

ok Correct position at 531239

Test #21:

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

input:

999991
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
18
19
18
19
20
20

output:

? 249997
? 749994
? 374996
? 624994
? 437495
? 562494
? 468744
? 531244
? 484368
? 515619
? 492180
? 507806
? 496086
? 503899
? 498039
? 501945
? 497062
? 502922
? 496573
? 503411
? 496329
? 503655
? 496207
? 503777
? 496146
? 503838
? 496115
? 503869
? 496100
? 503884
? 496092
? 503892
? 496088
? 5...

result:

ok Correct position at 503893

Test #22:

score: -100
Wrong Answer
time: 4ms
memory: 11508kb

input:

1000000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
25
26
27
28
27
28
27
28
27
28
27
27

output:

? 250000
? 750000
? 124999
? 875001
? 62499
? 937501
? 31249
? 968751
? 15624
? 984376
? 7811
? 992189
? 3905
? 996095
? 1952
? 998048
? 975
? 999025
? 487
? 999513
? 243
? 999757
? 121
? 999879
? 60
? 999940
? 29
? 999971
? 44
? 999955
? 36
? 999963
? 39
? 999959
? 40
? 999957
? 41
? 43
! 3

result:

wrong answer Wrong favorite light!
English 繁體中文 简体中文

Server Time: 2024-12-04 00:24:21 | OpenSource Project