QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#641138 | #5702. Colors | atgc | 0 | 1ms | 3596kb | C++23 | 1.1kb | 2024-10-14 18:48:39 | 2024-10-14 18:48: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 len=(n+1)/2;
int cur=0;int stp=0;
set<int>s;
while(len<n){
s.insert(cur);
if(stp^=1)cur+=len;
else cur-=len;
len=(1+len+n)/2;
}
int dta=*s.begin();
int l=1,r=n;
cur=-dta;stp=0;
set<int>qed;if(cur==0)++cur;
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);
if(cur+md>n)cur-=md;
else if(cur-md<=0)cur+=md;
else if(qed.count(cur+md))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: 3596kb
input:
7 1 1 0 0
output:
? 1 ? 5 ? 7 ? 4 = 4
result:
ok OK (4 queries)
Test #2:
score: 0
Wrong Answer
time: 1ms
memory: 3532kb
input:
49 0 0 0 0
output:
? 15 ? 40 ? 3 ? 46 ? 0
result:
wrong answer Integer parameter [name=k] equals to 0, violates the range [1, 49]
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%