QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#809665#9783. Duloc NetworkAfterlife#TL 1ms3648kbC++201.3kb2024-12-11 16:37:352024-12-11 16:38:49

Judging History

你现在查看的是最新测评结果

  • [2024-12-11 16:38:49]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3648kb
  • [2024-12-11 16:37:35]
  • 提交

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...

result: