QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#641166 | #5702. Colors | atgc | 0 | 1ms | 3872kb | C++23 | 1.5kb | 2024-10-14 18:56:46 | 2024-10-14 18:56:46 |
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 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(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: 0ms
memory: 3560kb
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: 3872kb
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: 0
Wrong Answer
time: 0ms
memory: 3624kb
input:
10 1 1 1 1 0
output:
? 4 ? 9 ? 6 ? 4 ? 5 = 2
result:
wrong answer Hair color 4 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%