QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#470386#6394. Turn on the LightUESTC_DebugSimulator#AC ✓1ms3812kbC++17880b2024-07-10 12:35:232024-07-10 12:35:23

Judging History

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

  • [2024-07-10 12:35:23]
  • 评测
  • 测评结果：AC
  • 用时：1ms
  • 内存：3812kb
查看
  • [2024-07-10 12:35:23]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define lowbit(i) (i&-i)
#define rand() (myrand())
using namespace std;
mt19937 myrand(time(0));
int n, x;
void ask(int k) {
	cout << "? " << k << endl;
	cin >> x;
}
void solve() {
	cin >> n;
	ask(1);
	if (!x) {
		cout << "! 1" << endl;
		return;
	}
	int l = 2, r = n, last = x;
	while(l < r) {
		int mid = (l + r)>>1;
		ask(mid);
		if (last == x) {
			cout << "! " << mid << endl;
			return;
		}
		if (last) {
			if (x > last) l = mid + 1;
			else r = mid;
		} 
		else {
			last = x;
			ask(l);
			if (last == x) {
				cout << "! " << l << endl;
				return;
			}
			l++;
			if (x < last) r = mid;
			else l = mid + 1;
		}
		last = x;
	}
	cout << "! " << l << endl;
}
signed main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	solve();
	return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1
2

output:

? 1
? 2
! 3

result:

ok Correct position at 3

Test #2:

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

input:

10
1
0
1
0
0

output:

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

result:

ok Correct position at 3

Test #3:

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

input:

9
1
2
3
3

output:

? 1
? 5
? 7
? 8
! 8

result:

ok Correct position at 8

Test #4:

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

input:

8
1
0
1
1

output:

? 1
? 5
? 3
? 2
! 2

result:

ok Correct position at 2

Test #5:

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

input:

7
1
2
3

output:

? 1
? 4
? 6
! 7

result:

ok Correct position at 7

Test #6:

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

input:

6
1
0
1
1

output:

? 1
? 4
? 3
? 2
! 2

result:

ok Correct position at 2

Test #7:

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

input:

5
1
2
3

output:

? 1
? 3
? 4
! 5

result:

ok Correct position at 5

Test #8:

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

input:

4
1
1

output:

? 1
? 3
! 3

result:

ok Correct position at 3

Test #9:

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

input:

3
1
1

output:

? 1
? 2
! 2

result:

ok Correct position at 2

Test #10:

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

input:

2
1

output:

? 1
! 2

result:

ok Correct position at 2

Test #11:

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

input:

1
0

output:

? 1
! 1

result:

ok Correct position at 1

Test #12:

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

input:

1000000
1
0
1
2
3
2
1
0
1
2
1
0
1
2
1
2
3
4
3
2
1
0
1
1

output:

? 1
? 500001
? 250001
? 2
? 375001
? 437501
? 406251
? 390626
? 382814
? 375002
? 386720
? 384767
? 383791
? 382815
? 384279
? 384035
? 384157
? 384218
? 384249
? 384234
? 384226
? 384222
? 384220
? 384219
! 384219

result:

ok Correct position at 384219

Test #13:

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

input:

999999
1
2
3
2
3
2
1
0
1
2
1
0
1
2
1
2
3
2
1
0
1
2
2

output:

? 1
? 500000
? 750000
? 875000
? 812500
? 843750
? 828125
? 820313
? 816407
? 812501
? 818360
? 817384
? 816896
? 816408
? 817140
? 817018
? 817079
? 817110
? 817095
? 817087
? 817083
? 817080
? 817085
! 817085

result:

ok Correct position at 817085

Test #14:

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

input:

999998
1
0
1
0
1
0
1
0
1
2
1
0
1
2
1
0
1
2
3
2
1
0
1
0
1
2
1
2
2

output:

? 1
? 500000
? 250001
? 2
? 125002
? 3
? 62503
? 4
? 31254
? 5
? 46879
? 39067
? 35161
? 31255
? 37114
? 36138
? 35650
? 35162
? 35894
? 36016
? 35955
? 35925
? 35910
? 35895
? 35903
? 35896
? 35907
? 35905
? 35906
! 35906

result:

ok Correct position at 35906

Test #15:

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

input:

999997
1
2
3
2
3
2
1
0
1
2
1
0
1
2
1
2
3
2
1
0
1
2
2

output:

? 1
? 499999
? 749998
? 874998
? 812498
? 843748
? 828123
? 820311
? 816405
? 812499
? 818358
? 817382
? 816894
? 816406
? 817138
? 817016
? 817077
? 817108
? 817093
? 817085
? 817081
? 817078
? 817083
! 817083

result:

ok Correct position at 817083

Test #16:

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

input:

999996
1
0
1
2
1
0
1
2
1
0
1
0
1
2
1
0
1
2
3
2
1
0
1
2
1
2
2

output:

? 1
? 499999
? 250000
? 2
? 375000
? 312500
? 281250
? 250001
? 296875
? 289063
? 285157
? 281251
? 283204
? 281252
? 284181
? 283693
? 283449
? 283205
? 283571
? 283632
? 283602
? 283587
? 283579
? 283572
? 283583
? 283581
? 283582
! 283582

result:

ok Correct position at 283582

Test #17:

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

input:

999995
1
2
3
4
5
4
3
2
1
0
1
2
1
0
1
2
3
2
1
0
1
2
2

output:

? 1
? 499998
? 749997
? 874996
? 937496
? 968746
? 953121
? 945309
? 941403
? 939450
? 938473
? 937497
? 938962
? 938718
? 938596
? 938474
? 938657
? 938688
? 938673
? 938665
? 938661
? 938658
? 938663
! 938663

result:

ok Correct position at 938663

Test #18:

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

input:

999994
1
0
1
0
1
2
1
0
1
2
1
0
1
2
1
0
1
2
3
2
1
0
1
2
1
2
2

output:

? 1
? 499998
? 250000
? 2
? 125001
? 3
? 187501
? 156251
? 140626
? 125002
? 148439
? 144533
? 142580
? 140627
? 143557
? 143069
? 142825
? 142581
? 142947
? 143008
? 142978
? 142963
? 142955
? 142948
? 142959
? 142957
? 142958
! 142958

result:

ok Correct position at 142958

Test #19:

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

input:

999993
1
2
3
4
5
4
3
2
1
0
1
2
1
0
1
2
3
2
1
0
1
2
2

output:

? 1
? 499997
? 749995
? 874994
? 937494
? 968744
? 953119
? 945307
? 941401
? 939448
? 938471
? 937495
? 938960
? 938716
? 938594
? 938472
? 938655
? 938686
? 938671
? 938663
? 938659
? 938656
? 938661
! 938661

result:

ok Correct position at 938661

Test #20:

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

input:

999992
1
0
1
2
3
2
1
0
1
2
1
0
1
2
1
2
3
4
3
2
1
0
1
1

output:

? 1
? 499997
? 249999
? 2
? 374998
? 437498
? 406248
? 390623
? 382811
? 374999
? 386717
? 384764
? 383788
? 382812
? 384276
? 384032
? 384154
? 384215
? 384246
? 384231
? 384223
? 384219
? 384217
? 384216
! 384216

result:

ok Correct position at 384216

Test #21:

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

input:

999991
1
2
3
2
1
0
1
2
1
0
1
0
1
2
1
2
3
4
3
2
1
0
1
1

output:

? 1
? 499996
? 749994
? 874993
? 812494
? 781244
? 765619
? 749995
? 773432
? 769526
? 767573
? 765620
? 766597
? 765621
? 767085
? 766841
? 766963
? 767024
? 767055
? 767040
? 767032
? 767028
? 767026
? 767025
! 767025

result:

ok Correct position at 767025

Test #22:

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

input:

1000000
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
3
4
4

output:

? 1
? 500001
? 250001
? 2
? 125002
? 3
? 62503
? 4
? 31254
? 5
? 15630
? 6
? 7818
? 7
? 3913
? 8
? 1961
? 9
? 985
? 10
? 498
? 11
? 255
? 12
? 134
? 13
? 74
? 14
? 44
? 15
? 30
? 16
? 37
? 41
? 43
! 43

result:

ok Correct position at 43

Test #23:

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

input:

999999
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
0
1
2
3
3

output:

? 1
? 500000
? 250001
? 2
? 125002
? 3
? 62503
? 4
? 31254
? 5
? 15630
? 6
? 7818
? 7
? 3913
? 8
? 1961
? 9
? 985
? 10
? 498
? 11
? 255
? 12
? 134
? 13
? 74
? 14
? 44
? 15
? 59
? 52
? 48
? 45
? 50
? 51
! 51

result:

ok Correct position at 51

Test #24:

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

input:

999998
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
0
1
2
3
3

output:

? 1
? 500000
? 250001
? 2
? 125002
? 3
? 62503
? 4
? 31254
? 5
? 15630
? 6
? 7818
? 7
? 3913
? 8
? 1961
? 9
? 985
? 10
? 498
? 11
? 255
? 12
? 134
? 13
? 74
? 14
? 44
? 15
? 59
? 52
? 48
? 45
? 50
? 51
! 51

result:

ok Correct position at 51

Test #25:

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

input:

999997
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
0
1
2
3
3

output:

? 1
? 499999
? 250000
? 2
? 125001
? 3
? 62502
? 4
? 31253
? 5
? 15629
? 6
? 7818
? 7
? 3913
? 8
? 1961
? 9
? 985
? 10
? 498
? 11
? 255
? 12
? 134
? 13
? 74
? 14
? 44
? 15
? 59
? 52
? 48
? 45
? 50
? 51
! 51

result:

ok Correct position at 51

Test #26:

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

input:

1000000
1
2
3
4
5
6
7
8
9
10
11
12
13
12
11
10
11
12
11
10
10

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992188
? 996094
? 998047
? 999024
? 999512
? 999756
? 999878
? 999817
? 999787
? 999772
? 999780
? 999784
? 999782
? 999781
! 999781

result:

ok Correct position at 999781

Test #27:

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

input:

999999
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
15
16
15
16
16

output:

? 1
? 500000
? 750000
? 875000
? 937500
? 968750
? 984375
? 992187
? 996093
? 998046
? 999023
? 999511
? 999755
? 999877
? 999938
? 999969
? 999984
? 999977
? 999981
? 999979
? 999980
! 999980

result:

ok Correct position at 999980

Test #28:

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

input:

999998
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
15
16
15
16
16

output:

? 1
? 500000
? 749999
? 874999
? 937499
? 968749
? 984374
? 992186
? 996092
? 998045
? 999022
? 999510
? 999754
? 999876
? 999937
? 999968
? 999983
? 999976
? 999980
? 999978
? 999979
! 999979

result:

ok Correct position at 999979

Test #29:

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

input:

999997
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
15
16
15
16
16

output:

? 1
? 499999
? 749998
? 874998
? 937498
? 968748
? 984373
? 992185
? 996091
? 998044
? 999021
? 999509
? 999753
? 999875
? 999936
? 999967
? 999982
? 999975
? 999979
? 999977
? 999978
! 999978

result:

ok Correct position at 999978

Test #30:

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

input:

1000000
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
13
12
11
12
13
13

output:

? 1
? 500001
? 250001
? 2
? 375001
? 437501
? 468751
? 484376
? 492189
? 496095
? 498048
? 499025
? 499513
? 499757
? 499879
? 499940
? 499971
? 499956
? 499948
? 499944
? 499946
? 499947
! 499947

result:

ok Correct position at 499947

Test #31:

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

input:

999999
1
2
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
3
4
5
5

output:

? 1
? 500000
? 750000
? 625000
? 562500
? 500001
? 531251
? 500002
? 515627
? 500003
? 507815
? 500004
? 503910
? 500005
? 501958
? 500006
? 500982
? 500007
? 500495
? 500008
? 500252
? 500009
? 500131
? 500010
? 500071
? 500011
? 500041
? 500012
? 500056
? 500064
? 500068
? 500070
! 500070

result:

ok Correct position at 500070

Test #32:

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

input:

999998
1
2
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
0
1
0
0

output:

? 1
? 500000
? 749999
? 625000
? 562500
? 500001
? 531251
? 500002
? 515627
? 500003
? 507815
? 500004
? 503910
? 500005
? 501958
? 500006
? 500982
? 500007
? 500495
? 500008
? 500252
? 500009
? 500131
? 500010
? 500071
? 500011
? 500101
? 500086
? 500079
? 500072
? 500076
! 500076

result:

ok Correct position at 500076

Test #33:

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

input:

999997
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
13
14
15
14
15
15

output:

? 1
? 499999
? 250000
? 2
? 375000
? 437500
? 468750
? 484375
? 492187
? 496093
? 498046
? 499023
? 499511
? 499755
? 499877
? 499938
? 499969
? 499954
? 499962
? 499966
? 499964
? 499965
! 499965

result:

ok Correct position at 499965

Test #34:

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

input:

1000000
1
0
1
2
1
0
1
2
1
0
1
0
1
2
1
0
1
0
1
2
1
0
1
0
1
0
1
0
0

output:

? 1
? 500001
? 250001
? 2
? 375001
? 312501
? 281251
? 250002
? 296876
? 289064
? 285158
? 281252
? 283205
? 281253
? 284182
? 283694
? 283450
? 283206
? 283328
? 283207
? 283389
? 283359
? 283344
? 283329
? 283337
? 283330
? 283334
? 283331
? 283333
! 283333

result:

ok Correct position at 283333

Test #35:

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

input:

999999
1
2
1
0
1
2
1
0
1
0
1
2
1
0
1
0
1
2
1
0
1
0
1
2
1
0
1
1

output:

? 1
? 500000
? 750000
? 625000
? 562500
? 500001
? 593750
? 578125
? 570313
? 562501
? 566407
? 562502
? 568360
? 567384
? 566896
? 566408
? 566652
? 566409
? 566774
? 566713
? 566683
? 566653
? 566668
? 566654
? 566676
? 566672
? 566670
? 566669
! 566669

result:

ok Correct position at 566669

Test #36:

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

input:

999998
1
0
1
0
1
0
1
0
1
0
1
0
1
2
1
0
1
0
1
2
1
0
1
2
1
0
1
2
1
0
0

output:

? 1
? 500000
? 250001
? 2
? 125002
? 3
? 62503
? 4
? 31254
? 5
? 15630
? 6
? 7818
? 7
? 11724
? 9771
? 8795
? 7819
? 8307
? 7820
? 8551
? 8429
? 8368
? 8308
? 8399
? 8384
? 8376
? 8369
? 8380
? 8378
? 8377
! 8377

result:

ok Correct position at 8377

Test #37:

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

input:

999997
1
2
3
2
1
0
1
2
1
0
1
0
1
0
1
2
1
0
1
2
1
0
1
2
1
0
0

output:

? 1
? 499999
? 749998
? 874998
? 812498
? 781248
? 765623
? 749999
? 773436
? 769530
? 767577
? 765624
? 766601
? 765625
? 766113
? 765626
? 766357
? 766235
? 766174
? 766114
? 766205
? 766190
? 766182
? 766175
? 766186
? 766184
? 766183
! 766183

result:

ok Correct position at 766183

Test #38:

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

input:

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

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992188
? 996094
? 998047
? 999024
? 999512
? 999756
? 999878
? 999939
? 999970
? 999985
? 999993
? 999997
? 999999
! 1000000

result:

ok Correct position at 1000000

Test #39:

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

input:

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

output:

? 1
? 500000
? 750000
? 875000
? 937500
? 968750
? 984375
? 992187
? 996093
? 998046
? 999023
? 999511
? 999755
? 999877
? 999938
? 999969
? 999984
? 999992
? 999996
? 999998
! 999999

result:

ok Correct position at 999999

Test #40:

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

input:

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

output:

? 1
? 500000
? 749999
? 874999
? 937499
? 968749
? 984374
? 992186
? 996092
? 998045
? 999022
? 999510
? 999754
? 999876
? 999937
? 999968
? 999983
? 999991
? 999995
? 999997
! 999998

result:

ok Correct position at 999998

Test #41:

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

input:

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

output:

? 1
? 499999
? 749998
? 874998
? 937498
? 968748
? 984373
? 992185
? 996091
? 998044
? 999021
? 999509
? 999753
? 999875
? 999936
? 999967
? 999982
? 999990
? 999994
? 999996
! 999997

result:

ok Correct position at 999997

Test #42:

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

input:

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

output:

? 1
? 500001
? 750001
? 875001
? 937501
? 968751
? 984376
? 992188
? 996094
? 998047
? 999024
? 999512
? 999756
? 999878
? 999939
? 999970
? 999985
? 999993
? 999997
? 999999
! 1000000

result:

ok Correct position at 1000000

Test #43:

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

input:

1000000
0

output:

? 1
! 1

result:

ok Correct position at 1
English 繁體中文 简体中文

Server Time: 2024-12-03 17:57:14 | OpenSource Project