QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#809665 | #9783. Duloc Network | Afterlife# | TL | 1ms | 3648kb | C++20 | 1.3kb | 2024-12-11 16:37:35 | 2024-12-11 16:38:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=205;
int n;
int Ask(bitset<N> b){
string s;
for(int i=1;i<=n;++i){
s+=char(b[i]+'0');
}
cout<<"? "<<s<<endl;
int x;
cin>>x;
return x;
}
void Report(int x){
cout<<"! "<<x<<endl;
exit(0);
}
int f[N],d[N];
bitset<N> b[N];
inline int getf(int x){
return f[x]==x?x:f[x]=getf(f[x]);
}
void Merge(int x,int y){
x=getf(x),y=getf(y);
f[y]=x;
b[x]|=b[y];
}
int a[N],m;
void Solve(int l,int r,int &u){
u=getf(u);
bitset<N> g=b[u];
int tot=d[u];
for(int i=l;i<=r;++i){
g|=b[a[i]];
tot+=d[a[i]];
}
int z=Ask(g);
if(z!=tot){
if(l==r){
Merge(a[l],u);
d[getf(u)]=d[getf(a[l])]=z;
return;
}
int mid=(l+r)>>1;
Solve(l,mid,u);
Solve(mid+1,r,u);
}
}
int main(){
cin>>n;
for(int i=1;i<=n;++i){
b[i][i]=1;
f[i]=i;
}
for(int i=1;i<=n;++i){
d[i]=Ask(b[i]);
m=0;
for(int j=1;j<i;++j){
if(getf(j)==j){
a[++m]=j;
}
}
if(m)Solve(1,m,i);
}
int cnt=0;
for(int i=1;i<=n;++i){
if(getf(i)==i){
++cnt;
}
}
Report(cnt==1);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3600kb
input:
4 1 3 2 2 1 2 0
output:
? 1000 ? 0100 ? 1100 ? 0010 ? 1110 ? 0001 ? 1111 ! 1
result:
ok Correct answer with 7 queries.
Test #2:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
2 0 0 0
output:
? 10 ? 01 ? 11 ! 0
result:
ok Correct answer with 3 queries.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3556kb
input:
4 1 3 2 2 1 2 0
output:
? 1000 ? 0100 ? 1100 ? 0010 ? 1110 ? 0001 ? 1111 ! 1
result:
ok Correct answer with 7 queries.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
2 0 0 0
output:
? 10 ? 01 ? 11 ! 0
result:
ok Correct answer with 3 queries.
Test #5:
score: -100
Time Limit Exceeded
input:
50 3 1 4 1 5 1 6 1 7 4 10 9 5 4 5 1 10 4 10 9 5 4 5 1 10 4 10 9 5 4 5 1 10 4 10 9 5 4 5 1 10 4 10 9 5 4 5 1 10 4 10 9 5 4 5 1 10 4 10 9 5 4 5 1 10 4 10 9 5 4 5 1 10 4 10 9 5 4 5 1 10 4 10 9 5 4 5 1 10 4 10 9 5 4 5 1 10 4 10 9 5 4 5 1 10 4 10 9 5 4 5 1 10 4 10 9 5 4 5 1 10 4 10 9 5 4 5 1 10 4 10 9 5 ...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 11000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 11100000000000000000000000000000000000000000000000 ? 000100000000000000000000000000000...