QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#43102 | #4306. Guess Matrix | perspective | AC ✓ | 360ms | 13540kb | C++17 | 1.8kb | 2022-08-07 17:48:23 | 2022-08-07 17:48:24 |
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|(1ll<<y)}))
x|=1ll<<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: 4ms
memory: 3808kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 3700kb
Test #3:
score: 0
Accepted
time: 2ms
memory: 3740kb
Test #4:
score: 0
Accepted
time: 4ms
memory: 3704kb
Test #5:
score: 0
Accepted
time: 4ms
memory: 3816kb
Test #6:
score: 0
Accepted
time: 4ms
memory: 3824kb
Test #7:
score: 0
Accepted
time: 4ms
memory: 3696kb
Test #8:
score: 0
Accepted
time: 5ms
memory: 3872kb
Test #9:
score: 0
Accepted
time: 0ms
memory: 3704kb
Test #10:
score: 0
Accepted
time: 3ms
memory: 3800kb
Test #11:
score: 0
Accepted
time: 3ms
memory: 3828kb
Test #12:
score: 0
Accepted
time: 49ms
memory: 4724kb
Test #13:
score: 0
Accepted
time: 0ms
memory: 3748kb
Test #14:
score: 0
Accepted
time: 101ms
memory: 5060kb
Test #15:
score: 0
Accepted
time: 46ms
memory: 5060kb
Test #16:
score: 0
Accepted
time: 276ms
memory: 13364kb
Test #17:
score: 0
Accepted
time: 314ms
memory: 13296kb
Test #18:
score: 0
Accepted
time: 351ms
memory: 13500kb
Test #19:
score: 0
Accepted
time: 350ms
memory: 13476kb
Test #20:
score: 0
Accepted
time: 318ms
memory: 13084kb
Test #21:
score: 0
Accepted
time: 324ms
memory: 13076kb
Test #22:
score: 0
Accepted
time: 269ms
memory: 13036kb
Test #23:
score: 0
Accepted
time: 257ms
memory: 11504kb
Test #24:
score: 0
Accepted
time: 356ms
memory: 11700kb
Test #25:
score: 0
Accepted
time: 297ms
memory: 11948kb
Test #26:
score: 0
Accepted
time: 359ms
memory: 12900kb
Test #27:
score: 0
Accepted
time: 308ms
memory: 12884kb
Test #28:
score: 0
Accepted
time: 277ms
memory: 10852kb
Test #29:
score: 0
Accepted
time: 316ms
memory: 13344kb
Test #30:
score: 0
Accepted
time: 275ms
memory: 13540kb
Test #31:
score: 0
Accepted
time: 346ms
memory: 13504kb
Test #32:
score: 0
Accepted
time: 360ms
memory: 13472kb
Test #33:
score: 0
Accepted
time: 358ms
memory: 13376kb
Test #34:
score: 0
Accepted
time: 305ms
memory: 13476kb
Test #35:
score: 0
Accepted
time: 224ms
memory: 9328kb