QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#178174 | #4306. Guess Matrix | Qingyu | AC ✓ | 160ms | 13408kb | C++20 | 1.8kb | 2023-09-13 18:58:55 | 2023-09-13 18:58:55 |
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: 1ms
memory: 3736kb
Test #2:
score: 0
Accepted
time: 1ms
memory: 3760kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3696kb
Test #4:
score: 0
Accepted
time: 1ms
memory: 3740kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 3760kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 3788kb
Test #7:
score: 0
Accepted
time: 1ms
memory: 3700kb
Test #8:
score: 0
Accepted
time: 1ms
memory: 3692kb
Test #9:
score: 0
Accepted
time: 1ms
memory: 3696kb
Test #10:
score: 0
Accepted
time: 3ms
memory: 3800kb
Test #11:
score: 0
Accepted
time: 0ms
memory: 3712kb
Test #12:
score: 0
Accepted
time: 23ms
memory: 4748kb
Test #13:
score: 0
Accepted
time: 1ms
memory: 3780kb
Test #14:
score: 0
Accepted
time: 11ms
memory: 4948kb
Test #15:
score: 0
Accepted
time: 10ms
memory: 5152kb
Test #16:
score: 0
Accepted
time: 138ms
memory: 13364kb
Test #17:
score: 0
Accepted
time: 141ms
memory: 13316kb
Test #18:
score: 0
Accepted
time: 117ms
memory: 13380kb
Test #19:
score: 0
Accepted
time: 134ms
memory: 13396kb
Test #20:
score: 0
Accepted
time: 110ms
memory: 12884kb
Test #21:
score: 0
Accepted
time: 134ms
memory: 13000kb
Test #22:
score: 0
Accepted
time: 131ms
memory: 12924kb
Test #23:
score: 0
Accepted
time: 108ms
memory: 11464kb
Test #24:
score: 0
Accepted
time: 105ms
memory: 11656kb
Test #25:
score: 0
Accepted
time: 117ms
memory: 11884kb
Test #26:
score: 0
Accepted
time: 117ms
memory: 12788kb
Test #27:
score: 0
Accepted
time: 140ms
memory: 12876kb
Test #28:
score: 0
Accepted
time: 107ms
memory: 10780kb
Test #29:
score: 0
Accepted
time: 155ms
memory: 13408kb
Test #30:
score: 0
Accepted
time: 126ms
memory: 13304kb
Test #31:
score: 0
Accepted
time: 160ms
memory: 13384kb
Test #32:
score: 0
Accepted
time: 146ms
memory: 13344kb
Test #33:
score: 0
Accepted
time: 141ms
memory: 13380kb
Test #34:
score: 0
Accepted
time: 126ms
memory: 13400kb
Test #35:
score: 0
Accepted
time: 105ms
memory: 9252kb