QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#35760 | #4306. Guess Matrix | Qingyu | WA | 19ms | 5084kb | C++ | 1.8kb | 2022-06-18 20:51:52 | 2023-09-13 18:58:21 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pii std::pair<int,ll>
#define sc second
#define fr first
int n;
std::set<pii> f;
inline bool qry(pii u){
int y=u.first;ll x=u.second;
for(int i=1;i<=y;i++)
if(f.count({i,x&((1ll<<i)-1)}))
return 0;
printf("? 1 %d\n",y);
for(int i=y-1;~i;i--)
putchar('0'+((x>>i)&1));
puts("");
fflush(stdout);
static int res;
scanf("%d",&res);
if(!res)
f.insert(u);
return res;
}
inline bool qq(std::deque<ll> u){
printf("? %d %d\n",u.size(),n);
for(auto x:u){
for(int i=n-1;~i;i--)
putchar('0'+((x>>i)&1));
puts("");
}
fflush(stdout);
static int res;
scanf("%d",&res);
return res;
}
std::vector<ll> p;
std::set<pii> s;
std::map<pii,bool> vis;
inline void sol(pii u){
int y=u.first;ll x=u.second;
for(;y<n;y++)
if(qry({y+1,x<<1}))
x<<=1;
else if(qry({y+1,x<<1|1}))
(x<<=1)|=1;
else
break;
for(;y<n;y++)
if(qry({y+1,x|(1<<y)}))
x|=1<<y;
p.push_back(x);
for(;y;y--,x>>=1)
for(int i=1;i<=y;i++){
auto tmp=std::make_pair(i,x&((1ll<<i)-1));
vis[tmp]=1;
s.insert(tmp);
}
}
std::deque<ll> q;
int main(){
scanf("%d",&n);
s.insert({0,0});
while(s.size()){
int y=s.begin()->first;
ll x=s.begin()->second;
s.erase(s.begin());
if(y==n)
continue;
if(!vis[{y+1,x<<1}]&&qry({y+1,x<<1}))
sol({y+1,x<<1});
if(!vis[{y+1,x<<1|1}]&&qry({y+1,x<<1|1}))
sol({y+1,x<<1|1});
}
q.push_back(p[0]);
while(q.size()<n){
bool flg=0;
for(auto x:p){
q.push_back(x);
if(qq(q)){
flg=1;
break;
}
q.pop_back();
}
if(!flg)
break;
}
while(q.size()<n){
for(auto x:p){
q.push_front(x);
if(qq(q))
break;
q.pop_front();
}
}
puts("!");
for(auto x:q){
for(int i=n-1;~i;i--)
putchar('0'+((x>>i)&1));
puts("");
}
}
Details
Test #1:
score: 100
Accepted
time: 1ms
memory: 3704kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 3692kb
Test #3:
score: 0
Accepted
time: 1ms
memory: 3740kb
Test #4:
score: 0
Accepted
time: 1ms
memory: 3696kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 3740kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 3696kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 3740kb
Test #8:
score: 0
Accepted
time: 1ms
memory: 3688kb
Test #9:
score: 0
Accepted
time: 1ms
memory: 3792kb
Test #10:
score: 0
Accepted
time: 3ms
memory: 3796kb
Test #11:
score: 0
Accepted
time: 1ms
memory: 3744kb
Test #12:
score: 0
Accepted
time: 19ms
memory: 4724kb
Test #13:
score: 0
Accepted
time: 0ms
memory: 3636kb
Test #14:
score: 0
Accepted
time: 15ms
memory: 4932kb
Test #15:
score: -100
Wrong Answer
time: 17ms
memory: 5084kb