QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#371563#6394. Turn on the LightzhoudashuaiAC ✓1ms3920kbC++141.3kb2024-03-30 14:01:292024-03-30 14:01:31

Judging History

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

  • [2024-03-30 14:01:31]
  • 评测
  • 测评结果：AC
  • 用时：1ms
  • 内存：3920kb
查看
  • [2024-03-30 14:01:29]
  • 提交

answer

#include<iostream>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<map>
#include<queue>
#include<set> 
#include<stack>
#include<bitset>
#include<unordered_map>
#include<iomanip>
#define endl '\n'
#define pb push_back
#define debug(x) cout<<x<<endl; 
#define me(a,x) memset(a,x,sizeof(a))
#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)

using namespace std;
typedef long long ll;
typedef pair<int ,int > PII;
typedef unsigned long long ull;
int a[55];
void solve(int l,int r,int cl,int cr){
	if(l==r){
		printf("! %d\n",l);
		fflush(stdout);
		return;
	}
	if(r==l+1){
		printf("? %d\n",l);
		fflush(stdout);
		int x;cin>>x;
		if(x==abs(cl-cr)){
			solve(l,l,cl,cr);
		}else{
			solve(r,r,cl+1,cr);
		}
		return ;
	}
	if(cl==cr){
		printf("? %d\n",r);
		fflush(stdout);
		int x;cin>>x;
		if(x==abs(cl-cr)){
			solve(r,r,cl,cr);
		}else{
			solve(l,r-1,cl,cr+1);
		}
	}
	else{
		int mid=l+r>>1;
		printf("? %d\n",mid);
		fflush(stdout);
		int x;cin>>x;
		if(x==abs(cl-cr)){
			solve(mid,mid,cl,cr);
		} else if(x==abs(cl-cr-1)){
			solve(l,mid-1,cl,cr+1);
		}else{
			solve(mid+1,r,cl+1,cr);
		}
	}
	
}
int main(){
	int n;cin>>n;
	solve(1,n,0,0);
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
0

output:

? 3
! 3

result:

ok Correct position at 3

Test #2:

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

input:

10
1
0
1
0

output:

? 10
? 5
? 9
? 7
! 8

result:

ok Correct position at 8

Test #3:

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

input:

9
1
0
1
0

output:

? 9
? 4
? 8
? 6
! 7

result:

ok Correct position at 7

Test #4:

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

input:

8
1
0
1
0

output:

? 8
? 4
? 7
? 5
! 6

result:

ok Correct position at 6

Test #5:

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

input:

7
1
0
1
0

output:

? 7
? 3
? 6
? 4
! 5

result:

ok Correct position at 5

Test #6:

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

input:

6
1
0
1

output:

? 6
? 3
? 4
! 5

result:

ok Correct position at 5

Test #7:

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

input:

5
1
0
1

output:

? 5
? 2
? 3
! 4

result:

ok Correct position at 4

Test #8:

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

input:

4
1
1

output:

? 4
? 2
! 2

result:

ok Correct position at 2

Test #9:

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

input:

3
1
0

output:

? 3
? 1
! 2

result:

ok Correct position at 2

Test #10:

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

input:

2
1

output:

? 1
! 2

result:

ok Correct position at 2

Test #11:

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

input:

1

output:

! 1

result:

ok Correct position at 1

Test #12:

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

input:

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

output:

? 1000000
? 500000
? 999999
? 749999
? 999998
? 874998
? 999997
? 937497
? 999996
? 968746
? 999995
? 984370
? 999994
? 992182
? 988276
? 990229
? 989252
? 989740
? 990228
? 989984
? 990227
? 990105
? 990226
? 990165
? 990225
? 990195
? 990180
? 990172
? 990176
? 990174
! 990175

result:

ok Correct position at 990175

Test #13:

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

input:

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

output:

? 999999
? 499999
? 999998
? 749998
? 999997
? 874997
? 999996
? 937496
? 999995
? 968745
? 999994
? 984369
? 999993
? 992181
? 988275
? 990228
? 989251
? 989739
? 990227
? 989983
? 990226
? 990104
? 990225
? 990164
? 990224
? 990194
? 990179
? 990171
? 990175
? 990173
! 990174

result:

ok Correct position at 990174

Test #14:

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

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

output:

? 999998
? 499999
? 999997
? 749998
? 999996
? 874997
? 999995
? 937496
? 999994
? 968745
? 953120
? 960932
? 968744
? 964838
? 962885
? 963861
? 964837
? 964349
? 964105
? 963983
? 964044
? 964074
? 964104
? 964089
? 964103
? 964096
? 964092
? 964094
! 964093

result:

ok Correct position at 964093

Test #15:

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

input:

999997
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

output:

? 999997
? 499998
? 999996
? 749997
? 999995
? 874996
? 999994
? 937495
? 999993
? 968744
? 953119
? 960931
? 968743
? 964837
? 962884
? 963860
? 964836
? 964348
? 964104
? 963982
? 964043
? 964073
? 964103
? 964088
? 964102
? 964095
? 964091
? 964093
! 964092

result:

ok Correct position at 964092

Test #16:

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

input:

999996
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

output:

? 999996
? 499998
? 999995
? 749996
? 999994
? 874995
? 999993
? 937494
? 999992
? 968743
? 953118
? 960930
? 968742
? 964836
? 962883
? 963859
? 964835
? 964347
? 964103
? 963981
? 964042
? 964072
? 964102
? 964087
? 964101
? 964094
? 964090
? 964092
! 964091

result:

ok Correct position at 964091

Test #17:

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

input:

999995
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

output:

? 999995
? 499997
? 999994
? 749995
? 999993
? 874994
? 999992
? 937493
? 999991
? 968742
? 953117
? 960929
? 968741
? 964835
? 962882
? 963858
? 964834
? 964346
? 964102
? 963980
? 964041
? 964071
? 964101
? 964086
? 964100
? 964093
? 964089
? 964091
! 964090

result:

ok Correct position at 964090

Test #18:

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

input:

999994
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

output:

? 999994
? 499997
? 999993
? 749995
? 999992
? 874993
? 999991
? 937492
? 999990
? 968741
? 953116
? 960928
? 968740
? 964834
? 962881
? 963857
? 964833
? 964345
? 964101
? 963979
? 964040
? 964070
? 964100
? 964085
? 964099
? 964092
? 964088
? 964090
! 964089

result:

ok Correct position at 964089

Test #19:

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

input:

999993
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

output:

? 999993
? 499996
? 999992
? 749994
? 999991
? 874992
? 999990
? 937491
? 999989
? 968740
? 953115
? 960927
? 968739
? 964833
? 962880
? 963856
? 964832
? 964344
? 964100
? 963978
? 964039
? 964069
? 964099
? 964084
? 964098
? 964091
? 964087
? 964089
! 964088

result:

ok Correct position at 964088

Test #20:

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

input:

999992
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

output:

? 999992
? 499996
? 999991
? 749993
? 999990
? 874991
? 999989
? 937490
? 999988
? 968739
? 953114
? 960926
? 968738
? 964832
? 962879
? 963855
? 964831
? 964343
? 964099
? 963977
? 964038
? 964068
? 964098
? 964083
? 964097
? 964090
? 964086
? 964088
! 964087

result:

ok Correct position at 964087

Test #21:

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

input:

999991
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

output:

? 999991
? 499995
? 999990
? 749992
? 999989
? 874990
? 999988
? 937489
? 999987
? 968738
? 953113
? 960925
? 968737
? 964831
? 962878
? 963854
? 964830
? 964342
? 964098
? 963976
? 964037
? 964067
? 964097
? 964082
? 964096
? 964089
? 964085
? 964087
! 964086

result:

ok Correct position at 964086

Test #22:

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

input:

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

output:

? 1000000
? 500000
? 250000
? 125000
? 62500
? 31250
? 15625
? 7812
? 3906
? 1953
? 976
? 488
? 244
? 122
? 61
? 30
? 45
? 37
? 41
? 43
! 43

result:

ok Correct position at 43

Test #23:

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

input:

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

output:

? 999999
? 499999
? 249999
? 124999
? 62499
? 31249
? 15624
? 7812
? 3906
? 1953
? 976
? 488
? 244
? 122
? 61
? 30
? 45
? 53
? 49
? 51
! 51

result:

ok Correct position at 51

Test #24:

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

input:

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

output:

? 999998
? 499999
? 249999
? 124999
? 62499
? 31249
? 15624
? 7812
? 3906
? 1953
? 976
? 488
? 244
? 122
? 61
? 30
? 45
? 53
? 49
? 51
! 51

result:

ok Correct position at 51

Test #25:

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

input:

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

output:

? 999997
? 499998
? 249999
? 124999
? 62499
? 31249
? 15624
? 7812
? 3906
? 1953
? 976
? 488
? 244
? 122
? 61
? 30
? 45
? 53
? 49
? 51
! 51

result:

ok Correct position at 51

Test #26:

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

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
2
3
2
3
4
3
2

output:

? 1000000
? 500000
? 999999
? 749999
? 999998
? 874998
? 999997
? 937497
? 999996
? 968746
? 999995
? 984370
? 999994
? 992182
? 999993
? 996087
? 999992
? 998039
? 999991
? 999015
? 999990
? 999502
? 999989
? 999745
? 999988
? 999866
? 999805
? 999775
? 999790
? 999782
? 999778
? 999780
! 999781

result:

ok Correct position at 999781

Test #27:

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

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
0
1
0
1
0
1
0
0

output:

? 999999
? 499999
? 999998
? 749998
? 999997
? 874997
? 999996
? 937496
? 999995
? 968745
? 999994
? 984369
? 999993
? 992181
? 999992
? 996086
? 999991
? 998038
? 999990
? 999014
? 999989
? 999501
? 999988
? 999744
? 999987
? 999865
? 999986
? 999925
? 999985
? 999955
? 999984
? 999969
? 999983
? 9...

result:

ok Correct position at 999980

Test #28:

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

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
0
1
0
1
0
1
0
0

output:

? 999998
? 499999
? 999997
? 749998
? 999996
? 874997
? 999995
? 937496
? 999994
? 968745
? 999993
? 984369
? 999992
? 992180
? 999991
? 996085
? 999990
? 998037
? 999989
? 999013
? 999988
? 999500
? 999987
? 999743
? 999986
? 999864
? 999985
? 999924
? 999984
? 999954
? 999983
? 999968
? 999982
? 9...

result:

ok Correct position at 999979

Test #29:

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

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
0
1
0
1
0
1
0
0

output:

? 999997
? 499998
? 999996
? 749997
? 999995
? 874996
? 999994
? 937495
? 999993
? 968744
? 999992
? 984368
? 999991
? 992179
? 999990
? 996084
? 999989
? 998036
? 999988
? 999012
? 999987
? 999499
? 999986
? 999742
? 999985
? 999863
? 999984
? 999923
? 999983
? 999953
? 999982
? 999967
? 999981
? 9...

result:

ok Correct position at 999978

Test #30:

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

input:

1000000
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
1
2
1
2

output:

? 1000000
? 500000
? 250000
? 375000
? 499999
? 437499
? 499998
? 468748
? 499997
? 484372
? 499996
? 492184
? 499995
? 496089
? 499994
? 498041
? 499993
? 499017
? 499992
? 499504
? 499991
? 499747
? 499990
? 499868
? 499989
? 499928
? 499988
? 499958
? 499943
? 499950
? 499946
? 499948
! 499947

result:

ok Correct position at 499947

Test #31:

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

input:

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

output:

? 999999
? 499999
? 999998
? 749998
? 624998
? 562498
? 531248
? 515623
? 507811
? 503905
? 501952
? 500975
? 500487
? 500243
? 500121
? 500060
? 500090
? 500075
? 500067
? 500071
? 500069
! 500070

result:

ok Correct position at 500070

Test #32:

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

input:

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

output:

? 999998
? 499999
? 999997
? 749998
? 624998
? 562498
? 531248
? 515623
? 507811
? 503905
? 501952
? 500975
? 500487
? 500243
? 500121
? 500060
? 500090
? 500075
? 500082
? 500078
? 500076
! 500076

result:

ok Correct position at 500076

Test #33:

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

input:

999997
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
0
1
2
1
2
1

output:

? 999997
? 499998
? 249999
? 374998
? 499997
? 437497
? 499996
? 468746
? 499995
? 484370
? 499994
? 492182
? 499993
? 496087
? 499992
? 498039
? 499991
? 499015
? 499990
? 499502
? 499989
? 499745
? 499988
? 499866
? 499987
? 499926
? 499986
? 499956
? 499985
? 499970
? 499963
? 499966
? 499964
! 4...

result:

ok Correct position at 499965

Test #34:

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

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
0
1
0
1
0
0

output:

? 1000000
? 500000
? 999999
? 749999
? 999998
? 874998
? 999997
? 937497
? 999996
? 968746
? 999995
? 984370
? 999994
? 992182
? 999993
? 996087
? 999992
? 998039
? 999991
? 999015
? 999990
? 999502
? 999989
? 999745
? 999988
? 999866
? 999987
? 999926
? 999986
? 999956
? 999985
? 999970
? 999984
? ...

result:

ok Correct position at 999981

Test #35:

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

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
0
1
0
1
0
1
0
0

output:

? 999999
? 499999
? 999998
? 749998
? 999997
? 874997
? 999996
? 937496
? 999995
? 968745
? 999994
? 984369
? 999993
? 992181
? 999992
? 996086
? 999991
? 998038
? 999990
? 999014
? 999989
? 999501
? 999988
? 999744
? 999987
? 999865
? 999986
? 999925
? 999985
? 999955
? 999984
? 999969
? 999983
? 9...

result:

ok Correct position at 999980

Test #36:

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

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
0
1
0
1
0
1
0
0

output:

? 999998
? 499999
? 999997
? 749998
? 999996
? 874997
? 999995
? 937496
? 999994
? 968745
? 999993
? 984369
? 999992
? 992180
? 999991
? 996085
? 999990
? 998037
? 999989
? 999013
? 999988
? 999500
? 999987
? 999743
? 999986
? 999864
? 999985
? 999924
? 999984
? 999954
? 999983
? 999968
? 999982
? 9...

result:

ok Correct position at 999979

Test #37:

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

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
0
1
0
1
0
1
0
0

output:

? 999997
? 499998
? 999996
? 749997
? 999995
? 874996
? 999994
? 937495
? 999993
? 968744
? 999992
? 984368
? 999991
? 992179
? 999990
? 996084
? 999989
? 998036
? 999988
? 999012
? 999987
? 999499
? 999986
? 999742
? 999985
? 999863
? 999984
? 999923
? 999983
? 999953
? 999982
? 999967
? 999981
? 9...

result:

ok Correct position at 999978

Test #38:

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

input:

1000000
1
2
3
4
5
6
7
6
5
4
5
4
3
2
1
2
1
2
3
4

output:

? 1000000
? 500000
? 250000
? 125000
? 62500
? 31250
? 15625
? 7812
? 11718
? 13671
? 14648
? 14159
? 14403
? 14525
? 14586
? 14617
? 14601
? 14609
? 14605
? 14603
! 14602

result:

ok Correct position at 14602

Test #39:

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

input:

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

output:

? 999999
? 499999
? 999998
? 749998
? 999997
? 874997
? 999996
? 937496
? 999995
? 968745
? 999994
? 984369
? 999993
? 992181
? 988275
? 986322
? 985345
? 985833
? 986077
? 986199
? 986321
? 986260
? 986229
? 986244
? 986259
? 986251
? 986258
? 986254
? 986257
? 986255
! 986255

result:

ok Correct position at 986255

Test #40:

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

input:

999998
1
2
1
2
3
4
5
4
3
2
3
2
1
0
1
2
1
0
1
0
1
0
1
1

output:

? 999998
? 499999
? 249999
? 374999
? 312499
? 281249
? 265624
? 257811
? 261717
? 263670
? 264647
? 264158
? 264402
? 264524
? 264646
? 264585
? 264554
? 264569
? 264584
? 264576
? 264583
? 264579
? 264582
? 264580
! 264580

result:

ok Correct position at 264580

Test #41:

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

input:

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

output:

? 999997
? 499998
? 999996
? 749997
? 624997
? 687497
? 656247
? 640622
? 632809
? 636715
? 638668
? 639645
? 639156
? 639400
? 639644
? 639522
? 639461
? 639430
? 639445
? 639453
? 639449
? 639447
! 639446

result:

ok Correct position at 639446

Test #42:

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

input:

1000000
0

output:

? 1000000
! 1000000

result:

ok Correct position at 1000000

Test #43:

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

input:

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

output:

? 1000000
? 500000
? 250000
? 125000
? 62500
? 31250
? 15625
? 7812
? 3906
? 1953
? 976
? 488
? 244
? 122
? 61
? 30
? 15
? 7
? 3
? 1
! 1

result:

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

Server Time: 2024-12-02 16:46:31 | OpenSource Project