QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#641170 | #5702. Colors | atgc | 0 | 1ms | 3836kb | C++23 | 1.5kb | 2024-10-14 18:58:42 | 2024-10-14 18:58:42 |
answer
#include<bits/stdc++.h>
#define int int64_t
using namespace std;
const int maxn = 2e5+10;
bool qry(int x){
cout<<"? "<<x<<endl;
bool res;cin>>res;return res;
}
void sol(){
int n;cin>>n;
int cur=0;
{
int l=1,r=n;
set<int>qed;
qed.insert(cur);
while(l<r){
int md=(l+r)>>1;
// if(stp^=1)cur+=md;
// else cur-=md;
// deb(cur+md,cur-md);
if(cur+md>n)cur-=md;
else if(cur-md<=0)cur+=md;
else assert(0);
// else if(qed.count(cur+md))cur-=md;
// else if(abs(cur+md-(1+n)/2.) < abs(cur-md-(1+n)/2.))cur+=md;
// else cur-=md;
qed.insert(cur);
if(0)r=md;
else l=md+1;
}
cur=1-*qed.begin();
}
int l=1,r=n;
set<int>qed;
qry(cur);qed.insert(cur);
while(l<r){
int md=(l+r)>>1;
// if(stp^=1)cur+=md;
// else cur-=md;
// deb(cur+md,cur-md);
while(cur+md>n&&cur-md<=0)--md;
if(cur+md>n)cur-=md;
else if(cur-md<=0)cur+=md;
else if(qed.count(cur+md))cur-=md;
else if(qed.count(cur-md))cur+=md;
else if(abs(cur+md-(1+n)/2.) < abs(cur-md-(1+n)/2.))cur+=md;
else cur-=md;
qed.insert(cur);
if(qry(cur))r=md;
else l=md+1;
}
cout<<"= "<<r<<endl;
}
signed main() {
// ios::sync_with_stdio(0),cin.tie(0);
// int T;cin>>T;while(T--)
sol();
// const int n=8;
// int len=n / 2;
// int cur=0;int stp=0;
// set<int>se;
// while(len < n){
// deb(len,cur);
// assert(se.insert(cur).second);
// if(stp^=1)cur+=len;
// else cur-=len;
// int nl=(1+len+n)/2;
// len=nl;
// }
// se.insert(cur);
// deb(se,se.size());
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 9
Accepted
time: 1ms
memory: 3484kb
input:
7 0 1 0 0
output:
? 3 ? 7 ? 5 ? 2 = 4
result:
ok OK (4 queries)
Test #2:
score: 9
Accepted
time: 1ms
memory: 3600kb
input:
49 1 0 0 0 1 1 0
output:
? 16 ? 41 ? 4 ? 47 ? 1 ? 46 ? 2 = 45
result:
ok OK (7 queries)
Test #3:
score: 9
Accepted
time: 0ms
memory: 3600kb
input:
10 1 1 1 1 0
output:
? 4 ? 9 ? 6 ? 8 ? 7 = 2
result:
ok OK (5 queries)
Test #4:
score: 9
Accepted
time: 1ms
memory: 3572kb
input:
26 0 1 1 1 1 1
output:
? 10 ? 23 ? 16 ? 12 ? 14 ? 13 = 1
result:
ok OK (6 queries)
Test #5:
score: 9
Accepted
time: 0ms
memory: 3604kb
input:
23 1 1 0 0 0
output:
? 8 ? 20 ? 14 ? 5 ? 16 = 12
result:
ok OK (5 queries)
Test #6:
score: 9
Accepted
time: 0ms
memory: 3580kb
input:
56 1 0 1 1 1 0 0
output:
? 19 ? 47 ? 5 ? 40 ? 8 ? 38 ? 7 = 32
result:
ok OK (7 queries)
Test #7:
score: 9
Accepted
time: 0ms
memory: 3792kb
input:
52 1 0 1 0 0 1 1
output:
? 17 ? 43 ? 4 ? 37 ? 1 ? 39 ? 2 = 37
result:
ok OK (7 queries)
Test #8:
score: 9
Accepted
time: 0ms
memory: 3536kb
input:
43 1 0 0 1 0 0
output:
? 15 ? 37 ? 4 ? 42 ? 6 ? 43 = 38
result:
ok OK (6 queries)
Test #9:
score: 9
Accepted
time: 0ms
memory: 3836kb
input:
46 0 0 0 1 0 1
output:
? 16 ? 39 ? 4 ? 45 ? 7 ? 46 = 39
result:
ok OK (6 queries)
Test #10:
score: 9
Accepted
time: 0ms
memory: 3536kb
input:
11 0 1 1 1 1
output:
? 4 ? 10 ? 7 ? 5 ? 6 = 1
result:
ok OK (5 queries)
Test #11:
score: 9
Accepted
time: 0ms
memory: 3600kb
input:
14 0 0 0 1 1
output:
? 5 ? 12 ? 1 ? 14 ? 2 = 12
result:
ok OK (5 queries)
Test #12:
score: 9
Accepted
time: 0ms
memory: 3796kb
input:
23 1 0 0 1 1 0
output:
? 8 ? 20 ? 2 ? 23 ? 3 ? 22 = 20
result:
ok OK (6 queries)
Test #13:
score: 9
Accepted
time: 1ms
memory: 3592kb
input:
47 1 0 0 1 1 1 0
output:
? 16 ? 40 ? 4 ? 46 ? 7 ? 45 ? 8 = 38
result:
ok OK (7 queries)
Test #14:
score: 9
Accepted
time: 0ms
memory: 3824kb
input:
44 0 0 1 0 1 1 0
output:
? 15 ? 37 ? 4 ? 32 ? 1 ? 31 ? 2 = 30
result:
ok OK (7 queries)
Test #15:
score: 9
Accepted
time: 0ms
memory: 3488kb
input:
54 1 0 0 1 1 0 0
output:
? 18 ? 45 ? 4 ? 52 ? 7 ? 50 ? 6 = 45
result:
ok OK (7 queries)
Test #16:
score: 9
Accepted
time: 1ms
memory: 3536kb
input:
53 0 1 0 1 0 0
output:
? 17 ? 44 ? 30 ? 9 ? 27 ? 7 = 21
result:
ok OK (6 queries)
Test #17:
score: 9
Accepted
time: 1ms
memory: 3596kb
input:
35 0 0 0 0 0 0
output:
? 12 ? 30 ? 3 ? 34 ? 1 ? 35 = 35
result:
ok OK (6 queries)
Test #18:
score: 9
Accepted
time: 0ms
memory: 3480kb
input:
37 0 0 1 1 0 1
output:
? 12 ? 31 ? 3 ? 27 ? 5 ? 28 = 23
result:
ok OK (6 queries)
Test #19:
score: 9
Accepted
time: 1ms
memory: 3820kb
input:
26 0 0 0 0 1 0
output:
? 10 ? 23 ? 3 ? 26 ? 1 ? 25 = 25
result:
ok OK (6 queries)
Test #20:
score: 9
Accepted
time: 1ms
memory: 3512kb
input:
64 1 0 1 1 1 0 1
output:
? 22 ? 54 ? 6 ? 46 ? 10 ? 44 ? 9 = 35
result:
ok OK (7 queries)
Test #21:
score: 9
Accepted
time: 0ms
memory: 3544kb
input:
57 0 0 0 1 0 0
output:
? 19 ? 48 ? 5 ? 55 ? 8 ? 57 = 50
result:
ok OK (6 queries)
Test #22:
score: 9
Accepted
time: 1ms
memory: 3792kb
input:
2 1 0
output:
? 1 ? 2 = 2
result:
ok OK (2 queries)
Test #23:
score: 9
Accepted
time: 1ms
memory: 3632kb
input:
2 1 1
output:
? 1 ? 2 = 1
result:
ok OK (2 queries)
Test #24:
score: 9
Accepted
time: 1ms
memory: 3596kb
input:
3 0 0
output:
? 1 ? 3 = 3
result:
ok OK (2 queries)
Test #25:
score: 9
Accepted
time: 1ms
memory: 3596kb
input:
3 0 1 0
output:
? 1 ? 3 ? 2 = 2
result:
ok OK (3 queries)
Test #26:
score: 9
Accepted
time: 1ms
memory: 3752kb
input:
3 0 1 1
output:
? 1 ? 3 ? 2 = 1
result:
ok OK (3 queries)
Test #27:
score: 9
Accepted
time: 1ms
memory: 3572kb
input:
4 0 0 0
output:
? 2 ? 4 ? 1 = 4
result:
ok OK (3 queries)
Test #28:
score: 9
Accepted
time: 0ms
memory: 3584kb
input:
4 0 0 1
output:
? 2 ? 4 ? 1 = 3
result:
ok OK (3 queries)
Test #29:
score: 9
Accepted
time: 1ms
memory: 3596kb
input:
4 0 1 0
output:
? 2 ? 4 ? 3 = 2
result:
ok OK (3 queries)
Test #30:
score: 9
Accepted
time: 1ms
memory: 3532kb
input:
4 0 1 1
output:
? 2 ? 4 ? 3 = 1
result:
ok OK (3 queries)
Test #31:
score: 9
Accepted
time: 1ms
memory: 3580kb
input:
5 1 0 0
output:
? 2 ? 5 ? 1 = 5
result:
ok OK (3 queries)
Test #32:
score: 9
Accepted
time: 0ms
memory: 3600kb
input:
5 1 0 1
output:
? 2 ? 5 ? 1 = 4
result:
ok OK (3 queries)
Test #33:
score: 9
Accepted
time: 0ms
memory: 3592kb
input:
5 1 1 0
output:
? 2 ? 5 ? 3 = 3
result:
ok OK (3 queries)
Test #34:
score: 9
Accepted
time: 0ms
memory: 3596kb
input:
5 1 1 1 0
output:
? 2 ? 5 ? 3 ? 4 = 2
result:
ok OK (4 queries)
Test #35:
score: 9
Accepted
time: 0ms
memory: 3760kb
input:
5 1 1 1 1
output:
? 2 ? 5 ? 3 ? 4 = 1
result:
ok OK (4 queries)
Test #36:
score: 9
Accepted
time: 0ms
memory: 3536kb
input:
6 1 0 0
output:
? 3 ? 6 ? 1 = 6
result:
ok OK (3 queries)
Test #37:
score: 9
Accepted
time: 0ms
memory: 3600kb
input:
6 1 0 1 0
output:
? 3 ? 6 ? 1 ? 5 = 5
result:
ok OK (4 queries)
Test #38:
score: 9
Accepted
time: 1ms
memory: 3600kb
input:
6 1 0 1 1
output:
? 3 ? 6 ? 1 ? 5 = 4
result:
ok OK (4 queries)
Test #39:
score: 9
Accepted
time: 1ms
memory: 3536kb
input:
6 1 1 0
output:
? 3 ? 6 ? 4 = 3
result:
ok OK (3 queries)
Test #40:
score: 9
Accepted
time: 1ms
memory: 3528kb
input:
6 1 1 1 0
output:
? 3 ? 6 ? 4 ? 5 = 2
result:
ok OK (4 queries)
Test #41:
score: 9
Accepted
time: 0ms
memory: 3832kb
input:
6 1 1 1 1
output:
? 3 ? 6 ? 4 ? 5 = 1
result:
ok OK (4 queries)
Test #42:
score: 9
Accepted
time: 0ms
memory: 3572kb
input:
7 0 0 0
output:
? 3 ? 7 ? 1 = 7
result:
ok OK (3 queries)
Test #43:
score: 9
Accepted
time: 0ms
memory: 3600kb
input:
7 0 0 1 0
output:
? 3 ? 7 ? 1 ? 6 = 6
result:
ok OK (4 queries)
Test #44:
score: 9
Accepted
time: 1ms
memory: 3484kb
input:
7 0 0 1 1
output:
? 3 ? 7 ? 1 ? 6 = 5
result:
ok OK (4 queries)
Test #45:
score: 9
Accepted
time: 0ms
memory: 3572kb
input:
7 0 1 0 0
output:
? 3 ? 7 ? 5 ? 2 = 4
result:
ok OK (4 queries)
Test #46:
score: 9
Accepted
time: 0ms
memory: 3832kb
input:
7 0 1 0 1
output:
? 3 ? 7 ? 5 ? 2 = 3
result:
ok OK (4 queries)
Test #47:
score: 9
Accepted
time: 0ms
memory: 3632kb
input:
7 0 1 1 0
output:
? 3 ? 7 ? 5 ? 4 = 2
result:
ok OK (4 queries)
Test #48:
score: 9
Accepted
time: 0ms
memory: 3568kb
input:
7 0 1 1 1
output:
? 3 ? 7 ? 5 ? 4 = 1
result:
ok OK (4 queries)
Test #49:
score: 9
Accepted
time: 0ms
memory: 3576kb
input:
8 1 0 0 0
output:
? 3 ? 7 ? 1 ? 8 = 8
result:
ok OK (4 queries)
Test #50:
score: 9
Accepted
time: 1ms
memory: 3660kb
input:
8 1 0 0 1
output:
? 3 ? 7 ? 1 ? 8 = 7
result:
ok OK (4 queries)
Test #51:
score: 9
Accepted
time: 0ms
memory: 3596kb
input:
8 1 0 1 0
output:
? 3 ? 7 ? 1 ? 6 = 6
result:
ok OK (4 queries)
Test #52:
score: 9
Accepted
time: 0ms
memory: 3832kb
input:
8 1 0 1 1
output:
? 3 ? 7 ? 1 ? 6 = 5
result:
ok OK (4 queries)
Test #53:
score: 9
Accepted
time: 0ms
memory: 3760kb
input:
8 1 1 0 0
output:
? 3 ? 7 ? 5 ? 2 = 4
result:
ok OK (4 queries)
Test #54:
score: 9
Accepted
time: 1ms
memory: 3532kb
input:
8 1 1 0 1
output:
? 3 ? 7 ? 5 ? 2 = 3
result:
ok OK (4 queries)
Test #55:
score: 9
Accepted
time: 0ms
memory: 3596kb
input:
8 1 1 1 0
output:
? 3 ? 7 ? 5 ? 4 = 2
result:
ok OK (4 queries)
Test #56:
score: 9
Accepted
time: 0ms
memory: 3604kb
input:
8 1 1 1 1
output:
? 3 ? 7 ? 5 ? 4 = 1
result:
ok OK (4 queries)
Test #57:
score: 9
Accepted
time: 0ms
memory: 3576kb
input:
18 0 0 0 0 1
output:
? 7 ? 16 ? 2 ? 18 ? 1 = 17
result:
ok OK (5 queries)
Test #58:
score: 9
Accepted
time: 0ms
memory: 3632kb
input:
18 0 0 0 0 0
output:
? 7 ? 16 ? 2 ? 18 ? 1 = 18
result:
ok OK (5 queries)
Test #59:
score: 9
Accepted
time: 0ms
memory: 3600kb
input:
37 0 0 0 0 0 1
output:
? 12 ? 31 ? 3 ? 36 ? 1 ? 37 = 36
result:
ok OK (6 queries)
Test #60:
score: 9
Accepted
time: 0ms
memory: 3596kb
input:
37 0 0 0 0 0 0
output:
? 12 ? 31 ? 3 ? 36 ? 1 ? 37 = 37
result:
ok OK (6 queries)
Test #61:
score: 9
Accepted
time: 0ms
memory: 3792kb
input:
63 1 1 1 1 1 1 1
output:
? 21 ? 53 ? 37 ? 29 ? 33 ? 31 ? 32 = 1
result:
ok OK (7 queries)
Test #62:
score: 9
Accepted
time: 0ms
memory: 3484kb
input:
63 1 0 0 0 0 0
output:
? 21 ? 53 ? 5 ? 61 ? 1 ? 63 = 63
result:
ok OK (6 queries)
Test #63:
score: 9
Accepted
time: 1ms
memory: 3540kb
input:
63 1 1 1 1 1 1 0
output:
? 21 ? 53 ? 37 ? 29 ? 33 ? 31 ? 32 = 2
result:
ok OK (7 queries)
Test #64:
score: 9
Accepted
time: 0ms
memory: 3640kb
input:
63 1 0 0 0 0 1 0
output:
? 21 ? 53 ? 5 ? 61 ? 1 ? 63 ? 2 = 62
result:
ok OK (7 queries)
Test #65:
score: 9
Accepted
time: 1ms
memory: 3488kb
input:
63 1 1 1 1 1 0 1
output:
? 21 ? 53 ? 37 ? 29 ? 33 ? 31 ? 34 = 3
result:
ok OK (7 queries)
Test #66:
score: 9
Accepted
time: 1ms
memory: 3536kb
input:
63 1 0 0 0 0 1 1
output:
? 21 ? 53 ? 5 ? 61 ? 1 ? 63 ? 2 = 61
result:
ok OK (7 queries)
Test #67:
score: 9
Accepted
time: 0ms
memory: 3628kb
input:
63 1 1 1 1 1 0 0
output:
? 21 ? 53 ? 37 ? 29 ? 33 ? 31 ? 34 = 4
result:
ok OK (7 queries)
Test #68:
score: 0
Wrong Answer
time: 0ms
memory: 3536kb
input:
63 1 0 0 0 1 0 0 0
output:
? 21 ? 53 ? 5 ? 61 ? 1 ? 59 ? 1 ? 60 = 60
result:
wrong answer Hair color 1 was used multiple times
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%