QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#43101 | #4306. Guess Matrix | perspective | WA | 101ms | 5216kb | C++17 | 1.8kb | 2022-08-07 17:13:16 | 2022-08-07 17:13:18 |
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: 3ms
memory: 3856kb
Test #2:
score: 0
Accepted
time: 2ms
memory: 3700kb
Test #3:
score: 0
Accepted
time: 3ms
memory: 3824kb
Test #4:
score: 0
Accepted
time: 4ms
memory: 3700kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 3828kb
Test #6:
score: 0
Accepted
time: 3ms
memory: 3828kb
Test #7:
score: 0
Accepted
time: 3ms
memory: 3752kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 3840kb
Test #9:
score: 0
Accepted
time: 4ms
memory: 3704kb
Test #10:
score: 0
Accepted
time: 7ms
memory: 3852kb
Test #11:
score: 0
Accepted
time: 2ms
memory: 3700kb
Test #12:
score: 0
Accepted
time: 28ms
memory: 4804kb
Test #13:
score: 0
Accepted
time: 12ms
memory: 3852kb
Test #14:
score: 0
Accepted
time: 32ms
memory: 5064kb
Test #15:
score: -100
Wrong Answer
time: 101ms
memory: 5216kb