QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #138372 | #6394. Turn on the Light | Schi2oid | WA | 5ms | 11500kb | C++14 | 945b | 2023-08-11 16:44:59 | 2023-08-11 16:45:02 |
Judging History
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){
n=p2-p1;
int cnt=0;
for(int i=p1+1;i<p2;i++){
id[op][++cnt]=id[op^1][i];
}
}
else{
n=n-p2+p1-1;
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];
}
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3460kb
input:
3 1 2 2
output:
? 1 ? 2 ? 3 ! 3
result:
ok Correct position at 3
Test #2:
score: 0
Accepted
time: 2ms
memory: 5668kb
input:
10 1 0 1 0 1 0 0
output:
? 2 ? 8 ? 3 ? 7 ? 4 ? 6 ? 5 ! 5
result:
ok Correct position at 5
Test #3:
score: 0
Accepted
time: 2ms
memory: 5620kb
input:
9 1 0 1 0 1 1
output:
? 2 ? 7 ? 3 ? 6 ? 4 ? 5 ! 5
result:
ok Correct position at 5
Test #4:
score: 0
Accepted
time: 1ms
memory: 5672kb
input:
8 1 0 1 0 0
output:
? 2 ? 6 ? 3 ? 5 ? 4 ! 4
result:
ok Correct position at 4
Test #5:
score: 0
Accepted
time: 0ms
memory: 5632kb
input:
7 1 0 1 0 1 1
output:
? 1 ? 6 ? 2 ? 5 ? 3 ? 4 ! 4
result:
ok Correct position at 4
Test #6:
score: 0
Accepted
time: 1ms
memory: 5508kb
input:
6 1 0 1 0 0
output:
? 1 ? 5 ? 2 ? 4 ? 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: 0ms
memory: 3472kb
input:
4 1 1
output:
? 1 ? 3 ! 3
result:
ok Correct position at 3
Test #9:
score: 0
Accepted
time: 1ms
memory: 3472kb
input:
3 1 1
output:
? 1 ? 2 ! 2
result:
ok Correct position at 2
Test #10:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
2 1 1
output:
? 1 ? 2 ! 2
result:
ok Correct position at 2
Test #11:
score: 0
Accepted
time: 1ms
memory: 3340kb
input:
1 0
output:
? 1 ! 1
result:
ok Correct position at 1
Test #12:
score: -100
Wrong Answer
time: 5ms
memory: 11500kb
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 1 1
output:
? 250000 ? 750000 ? 375000 ? 625000 ? 437500 ? 562500 ? 468750 ? 531250 ? 484375 ? 515625 ? 492187 ? 507813 ? 496093 ? 503907 ? 498046 ? 501954 ? 499023 ? 500977 ? 499511 ? 500489 ? 499755 ? 500245 ? 499877 ? 500123 ? 499938 ? 500062 ? 499969 ? 500031 ? 499984 ? 500016 ? 499992 ? 500008 ? 499996 ? 5...
result:
wrong answer Wrong favorite light!