QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#117491 | #6394. Turn on the Light | installb# | AC ✓ | 3ms | 3812kb | C++14 | 710b | 2023-07-01 13:39:59 | 2023-07-01 13:40:00 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,r,l) for(int i=(r);i>=(l);--i)
using namespace std;
int n;
int ask(int x){
int ans=0;
printf("? %d\n",x);fflush(stdout);
scanf("%d",&ans);
return ans;
}
void report(int x){
printf("! %d\n",x);fflush(stdout);
exit(0);
}
int main(){
scanf("%d",&n);
int l=1,r=n,x=0;
while(l<r){
if(x==0){
if(ask(l)) x=1,++l;
else report(l);
}
int mid=(l+r)>>1;
int cur=ask(mid);
if(abs(x)==cur) report(mid);
else if(abs(x-1)==cur) r=mid-1,--x;
else l=mid+1,++x;
}
report(l);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3628kb
input:
3 1 2
output:
? 1 ? 2 ! 3
result:
ok Correct position at 3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
10 1 0 1 0
output:
? 1 ? 6 ? 2 ? 4 ! 3
result:
ok Correct position at 3
Test #3:
score: 0
Accepted
time: 0ms
memory: 3572kb
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: 3768kb
input:
8 1 0 1 1
output:
? 1 ? 5 ? 2 ? 3 ! 3
result:
ok Correct position at 3
Test #5:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
7 1 2 3
output:
? 1 ? 4 ? 6 ! 7
result:
ok Correct position at 7
Test #6:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
6 1 0 1 1
output:
? 1 ? 4 ? 2 ? 3 ! 3
result:
ok Correct position at 3
Test #7:
score: 0
Accepted
time: 0ms
memory: 3516kb
input:
5 1 2 3
output:
? 1 ? 3 ? 4 ! 5
result:
ok Correct position at 5
Test #8:
score: 0
Accepted
time: 1ms
memory: 3636kb
input:
4 1 1
output:
? 1 ? 3 ! 3
result:
ok Correct position at 3
Test #9:
score: 0
Accepted
time: 2ms
memory: 3768kb
input:
3 1 1
output:
? 1 ? 2 ! 2
result:
ok Correct position at 2
Test #10:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
2 1 1
output:
? 1 ? 2 ! 2
result:
ok Correct position at 2
Test #11:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
1
output:
! 1
result:
ok Correct position at 1
Test #12:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
1000000 1 0 1 2 3 2 1 0 1 2 1 0 1 2 1 2 3 4 5 6 5 4 4
output:
? 1 ? 500001 ? 2 ? 250001 ? 375001 ? 437501 ? 406251 ? 390626 ? 375002 ? 382814 ? 386720 ? 384767 ? 382815 ? 383791 ? 384279 ? 384035 ? 384157 ? 384218 ? 384248 ? 384263 ? 384271 ? 384267 ? 384265 ! 384265
result:
ok Correct position at 384265
Test #13:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
999999 1 2 3 2 3 2 1 2 3 4 3 4 5 6 7 8 9 10 11 12
output:
? 1 ? 500000 ? 750000 ? 875000 ? 812500 ? 843750 ? 828125 ? 820312 ? 824218 ? 826171 ? 827148 ? 826659 ? 826903 ? 827025 ? 827086 ? 827117 ? 827132 ? 827140 ? 827144 ? 827146 ! 827147
result:
ok Correct position at 827147
Test #14:
score: 0
Accepted
time: 3ms
memory: 3576kb
input:
999998 1 0 1 0 1 0 1 0 1 2 3 4 5 6 5 6 7 8 9 8 9 8 9 8
output:
? 1 ? 500000 ? 2 ? 250001 ? 3 ? 125002 ? 4 ? 62503 ? 5 ? 31254 ? 46878 ? 54690 ? 58596 ? 60549 ? 61526 ? 61037 ? 61281 ? 61403 ? 61464 ? 61495 ? 61479 ? 61487 ? 61483 ? 61485 ! 61484
result:
ok Correct position at 61484
Test #15:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
999997 1 2 3 2 3 2 1 2 3 4 3 4 5 6 7 8 9 10 11 12
output:
? 1 ? 499999 ? 749998 ? 874998 ? 812498 ? 843748 ? 828123 ? 820310 ? 824216 ? 826169 ? 827146 ? 826657 ? 826901 ? 827023 ? 827084 ? 827115 ? 827130 ? 827138 ? 827142 ? 827144 ! 827145
result:
ok Correct position at 827145
Test #16:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
999996 1 0 1 2 3 2 1 0 1 2 1 0 1 2 1 2 3 4 5 6 5 4 4
output:
? 1 ? 499999 ? 2 ? 250000 ? 374999 ? 437499 ? 406249 ? 390624 ? 375000 ? 382812 ? 386718 ? 384765 ? 382813 ? 383789 ? 384277 ? 384033 ? 384155 ? 384216 ? 384246 ? 384261 ? 384269 ? 384265 ? 384263 ! 384263
result:
ok Correct position at 384263
Test #17:
score: 0
Accepted
time: 2ms
memory: 3812kb
input:
999995 1 2 3 4 5 4 3 4 5 6 5 6 7 8 9 10 11 12 13 14
output:
? 1 ? 499998 ? 749997 ? 874996 ? 937496 ? 968746 ? 953121 ? 945308 ? 949214 ? 951167 ? 952144 ? 951655 ? 951899 ? 952021 ? 952082 ? 952113 ? 952128 ? 952136 ? 952140 ? 952142 ! 952143
result:
ok Correct position at 952143
Test #18:
score: 0
Accepted
time: 2ms
memory: 3620kb
input:
999994 1 0 1 0 1 2 3 2 1 2 3 4 5 6 7 8 9 10 11 10 9 10
output:
? 1 ? 499998 ? 2 ? 250000 ? 3 ? 125001 ? 187500 ? 218750 ? 203125 ? 195312 ? 199218 ? 201171 ? 202148 ? 202636 ? 202880 ? 203002 ? 203063 ? 203094 ? 203109 ? 203117 ? 203113 ? 203111 ! 203112
result:
ok Correct position at 203112
Test #19:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
999993 1 2 3 4 5 4 3 4 5 6 5 6 7 8 9 10 11 12 13 14
output:
? 1 ? 499997 ? 749995 ? 874994 ? 937494 ? 968744 ? 953119 ? 945306 ? 949212 ? 951165 ? 952142 ? 951653 ? 951897 ? 952019 ? 952080 ? 952111 ? 952126 ? 952134 ? 952138 ? 952140 ! 952141
result:
ok Correct position at 952141
Test #20:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
999992 1 0 1 2 3 4 3 2 3 4 5 4 5 6 7 8 9 10 11 10 11
output:
? 1 ? 499997 ? 2 ? 249999 ? 374998 ? 437497 ? 468747 ? 453122 ? 445309 ? 449215 ? 451168 ? 452145 ? 451656 ? 451900 ? 452022 ? 452083 ? 452114 ? 452129 ? 452137 ? 452141 ? 452139 ! 452140
result:
ok Correct position at 452140
Test #21:
score: 0
Accepted
time: 2ms
memory: 3796kb
input:
999991 1 2 3 2 3 2 1 2 3 4 3 4 5 6 7 8 9 10 11 12
output:
? 1 ? 499996 ? 749994 ? 874993 ? 812493 ? 843743 ? 828118 ? 820305 ? 824211 ? 826164 ? 827141 ? 826652 ? 826896 ? 827018 ? 827079 ? 827110 ? 827125 ? 827133 ? 827137 ? 827139 ! 827140
result:
ok Correct position at 827140
Test #22:
score: 0
Accepted
time: 3ms
memory: 3576kb
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 5
output:
? 1 ? 500001 ? 2 ? 250001 ? 3 ? 125002 ? 4 ? 62503 ? 5 ? 31254 ? 6 ? 15630 ? 7 ? 7818 ? 8 ? 3913 ? 9 ? 1961 ? 10 ? 985 ? 11 ? 498 ? 12 ? 255 ? 13 ? 134 ? 14 ? 74 ? 15 ? 44 ? 16 ? 30 ? 37 ? 40 ? 42 ! 43
result:
ok Correct position at 43
Test #23:
score: 0
Accepted
time: 0ms
memory: 3584kb
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 1
output:
? 1 ? 500000 ? 2 ? 250001 ? 3 ? 125002 ? 4 ? 62503 ? 5 ? 31254 ? 6 ? 15630 ? 7 ? 7818 ? 8 ? 3913 ? 9 ? 1961 ? 10 ? 985 ? 11 ? 498 ? 12 ? 255 ? 13 ? 134 ? 14 ? 74 ? 15 ? 44 ? 59 ? 51 ! 51
result:
ok Correct position at 51
Test #24:
score: 0
Accepted
time: 0ms
memory: 3808kb
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 1
output:
? 1 ? 500000 ? 2 ? 250001 ? 3 ? 125002 ? 4 ? 62503 ? 5 ? 31254 ? 6 ? 15630 ? 7 ? 7818 ? 8 ? 3913 ? 9 ? 1961 ? 10 ? 985 ? 11 ? 498 ? 12 ? 255 ? 13 ? 134 ? 14 ? 74 ? 15 ? 44 ? 59 ? 51 ! 51
result:
ok Correct position at 51
Test #25:
score: 0
Accepted
time: 3ms
memory: 3636kb
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 1
output:
? 1 ? 499999 ? 2 ? 250000 ? 3 ? 125001 ? 4 ? 62502 ? 5 ? 31253 ? 6 ? 15629 ? 7 ? 7818 ? 8 ? 3913 ? 9 ? 1961 ? 10 ? 985 ? 11 ? 498 ? 12 ? 255 ? 13 ? 134 ? 14 ? 74 ? 15 ? 44 ? 59 ? 51 ! 51
result:
ok Correct position at 51
Test #26:
score: 0
Accepted
time: 2ms
memory: 3556kb
input:
1000000 1 2 3 4 5 6 7 8 9 10 11 12 13 12 11 10 11 12 11 12
output:
? 1 ? 500001 ? 750001 ? 875001 ? 937501 ? 968751 ? 984376 ? 992188 ? 996094 ? 998047 ? 999024 ? 999512 ? 999756 ? 999878 ? 999817 ? 999786 ? 999771 ? 999778 ? 999782 ? 999780 ! 999781
result:
ok Correct position at 999781
Test #27:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
999999 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 15 16 16
output:
? 1 ? 500000 ? 750000 ? 875000 ? 937500 ? 968750 ? 984375 ? 992187 ? 996093 ? 998046 ? 999023 ? 999511 ? 999755 ? 999877 ? 999938 ? 999969 ? 999984 ? 999976 ? 999980 ! 999980
result:
ok Correct position at 999980
Test #28:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
999998 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 15 16 16
output:
? 1 ? 500000 ? 749999 ? 874999 ? 937499 ? 968749 ? 984374 ? 992186 ? 996092 ? 998045 ? 999022 ? 999510 ? 999754 ? 999876 ? 999937 ? 999968 ? 999983 ? 999975 ? 999979 ! 999979
result:
ok Correct position at 999979
Test #29:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
999997 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 15 16 16
output:
? 1 ? 499999 ? 749998 ? 874998 ? 937498 ? 968748 ? 984373 ? 992185 ? 996091 ? 998044 ? 999021 ? 999509 ? 999753 ? 999875 ? 999936 ? 999967 ? 999982 ? 999974 ? 999978 ! 999978
result:
ok Correct position at 999978
Test #30:
score: 0
Accepted
time: 2ms
memory: 3564kb
input:
1000000 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 13 12 13 12 11
output:
? 1 ? 500001 ? 2 ? 250001 ? 375001 ? 437501 ? 468751 ? 484376 ? 492188 ? 496094 ? 498047 ? 499024 ? 499512 ? 499756 ? 499878 ? 499939 ? 499970 ? 499954 ? 499946 ? 499950 ? 499948 ! 499947
result:
ok Correct position at 499947
Test #31:
score: 0
Accepted
time: 2ms
memory: 3512kb
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 6
output:
? 1 ? 500000 ? 750000 ? 625000 ? 500001 ? 562500 ? 500002 ? 531251 ? 500003 ? 515627 ? 500004 ? 507815 ? 500005 ? 503910 ? 500006 ? 501958 ? 500007 ? 500982 ? 500008 ? 500495 ? 500009 ? 500252 ? 500010 ? 500131 ? 500011 ? 500071 ? 500012 ? 500041 ? 500056 ? 500063 ? 500067 ? 500069 ! 500070
result:
ok Correct position at 500070
Test #32:
score: 0
Accepted
time: 3ms
memory: 3764kb
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 1 1
output:
? 1 ? 500000 ? 749999 ? 624999 ? 500001 ? 562500 ? 500002 ? 531251 ? 500003 ? 515627 ? 500004 ? 507815 ? 500005 ? 503910 ? 500006 ? 501958 ? 500007 ? 500982 ? 500008 ? 500495 ? 500009 ? 500252 ? 500010 ? 500131 ? 500011 ? 500071 ? 500101 ? 500086 ? 500072 ? 500079 ? 500073 ? 500076 ! 500076
result:
ok Correct position at 500076
Test #33:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
999997 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 13 14 15 16 15
output:
? 1 ? 499999 ? 2 ? 250000 ? 374999 ? 437499 ? 468749 ? 484374 ? 492186 ? 496092 ? 498045 ? 499022 ? 499510 ? 499754 ? 499876 ? 499937 ? 499968 ? 499952 ? 499960 ? 499964 ? 499966 ! 499965
result:
ok Correct position at 499965
Test #34:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
1000000 1 0 1 2 1 0 1 2 1 2 3 4 3 4 5 6 7 6 7 6 5 4
output:
? 1 ? 500001 ? 2 ? 250001 ? 375001 ? 312501 ? 250002 ? 281251 ? 296876 ? 289063 ? 292969 ? 294922 ? 295899 ? 295410 ? 295654 ? 295776 ? 295837 ? 295868 ? 295852 ? 295860 ? 295856 ? 295854 ! 295853
result:
ok Correct position at 295853
Test #35:
score: 0
Accepted
time: 3ms
memory: 3792kb
input:
999999 1 2 1 0 1 2 1 0 1 0 1 2 1 2 3 4 5 6 5 6 5 4 3
output:
? 1 ? 500000 ? 750000 ? 625000 ? 500001 ? 562500 ? 593750 ? 578125 ? 562501 ? 570313 ? 562502 ? 566407 ? 568360 ? 567383 ? 567871 ? 568115 ? 568237 ? 568298 ? 568329 ? 568313 ? 568321 ? 568317 ? 568315 ! 568314
result:
ok Correct position at 568314
Test #36:
score: 0
Accepted
time: 2ms
memory: 3796kb
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 3 4 3 2 1
output:
? 1 ? 500000 ? 2 ? 250001 ? 3 ? 125002 ? 4 ? 62503 ? 5 ? 31254 ? 6 ? 15630 ? 7 ? 7818 ? 11724 ? 9771 ? 7819 ? 8795 ? 7820 ? 8307 ? 8551 ? 8429 ? 8308 ? 8368 ? 8398 ? 8413 ? 8421 ? 8417 ? 8415 ! 8414
result:
ok Correct position at 8414
Test #37:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
999997 1 2 3 2 1 0 1 2 3 4 5 4 5 6 7 8 7 8 7 6 5
output:
? 1 ? 499999 ? 749998 ? 874998 ? 812498 ? 781248 ? 749999 ? 765623 ? 773435 ? 777341 ? 779294 ? 780271 ? 779782 ? 780026 ? 780148 ? 780209 ? 780240 ? 780224 ? 780232 ? 780228 ? 780226 ! 780225
result:
ok Correct position at 780225
Test #38:
score: 0
Accepted
time: 2ms
memory: 3652kb
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: 2ms
memory: 3812kb
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: 2ms
memory: 3572kb
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: 2ms
memory: 3572kb
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: 0ms
memory: 3764kb
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: 3792kb
input:
1000000 0
output:
? 1 ! 1
result:
ok Correct position at 1