QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#774248 | #9783. Duloc Network | ucup-team3555# | WA | 14ms | 4896kb | C++20 | 1.7kb | 2024-11-23 12:39:28 | 2024-11-23 12:39:29 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=203;
int n,f[N],ans[N];
map<vector<int>,int>mp;
void NB(int x){cout<<"! "<<x<<endl;exit(0);}
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
bool Chk()
{
for(int i=1;i<=n;i++)if(F(i)==F(1))return 0;
return 1;
}
int Ask(vector<int>v)
{
vector<int>vis(n+1,0);
for(int x:v)vis[x]=1;
if(mp.count(vis))return mp[vis];
cout<<"? ";
for(int i=1;i<=n;i++)cout<<vis[i];
cout<<endl;
int s;cin>>s;return mp[vis]=s;
}
void Mer(int x,int y)
{
x=F(x);y=F(y);
if(x==y)return;
vector<int>ask;ans[y]=0;f[F(y)]=F(x);
for(int i=1;i<=n;i++)if(F(i)==F(x))ask.push_back(i);
ans[x]=Ask(ask);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)f[i]=i,ans[i]=Ask({i});
while(1)
{
vector<int>ve;int sz=0,all=0;
for(int i=1;i<=n;i++)if(F(i)==i)ve.push_back(i),sz++,all+=ans[i];
if(sz==1)NB(1);
int s=Ask(ve);
if(s==all)NB(0);
vector<array<int,2>>nb;
for(int i=0;i<sz;i++)
{
vector<int>v;
for(int j=0;j<sz;j++)if(j!=i)v.push_back(ve[j]);
while(v.size()>1)
{
int mid=v.size()/2,sum=0;vector<int>ask;
for(int j=0;j<mid;j++)ask.push_back(v[j]),sum+=ans[v[j]];
sum+=ans[ve[i]];
ll v0=Ask(ask);
ask.push_back(ve[i]);
ll v1=Ask(ask);
ask.pop_back();
if(v0+ans[ve[i]]>v1){v=ask;continue;}
ask.clear();sum=0;
for(int j=mid;j<(int)v.size();j++)ask.push_back(v[j]),sum+=ans[v[j]];
sum+=ans[ve[i]];
v0=Ask(ask);
ask.push_back(ve[i]);
v1=Ask(ask);
ask.pop_back();
if(v0+ans[ve[i]]>v1){v=ask;continue;}
NB(0);
}
if(Ask({ve[i],v[0]})<ans[ve[i]]+ans[v[0]])nb.push_back({ve[i],v[0]});
}
for(auto t:nb)Mer(t[0],t[1]);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3600kb
input:
4 1 3 2 2 0 2 2 2 1
output:
? 1000 ? 0100 ? 0010 ? 0001 ? 1111 ? 1100 ? 1010 ? 1001 ? 1110 ! 1
result:
ok Correct answer with 9 queries.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3768kb
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: 3768kb
input:
4 1 3 2 2 0 2 2 2 1
output:
? 1000 ? 0100 ? 0010 ? 0001 ? 1111 ? 1100 ? 1010 ? 1001 ? 1110 ! 1
result:
ok Correct answer with 9 queries.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
2 0 0 0
output:
? 10 ? 01 ? 11 ! 0
result:
ok Correct answer with 3 queries.
Test #5:
score: 0
Accepted
time: 5ms
memory: 3988kb
input:
50 3 1 1 1 1 4 3 1 1 2 3 3 2 1 2 4 3 1 1 1 2 4 1 3 1 4 3 2 2 2 4 2 2 1 1 2 1 2 4 1 1 3 3 3 6 2 1 3 2 3 0 14 15 14 15 8 11 9 10 4 7 8 9 6 5 6 6 3 16 16 12 5 6 8 7 2 7 6 5 2 15 14 16 16 12 13 10 10 6 7 5 5 2 4 4 3 15 15 11 5 8 2 7 4 16 14 15 11 7 6 2 6 5 3 3 16 15 8 9 5 15 14 10 6 6 2 3 16 15 11 12 12...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 514 queries.
Test #6:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
50 10 13 8 6 13 8 10 8 8 8 9 13 15 11 9 10 14 6 16 10 15 10 7 8 10 10 10 13 10 15 9 10 11 5 16 10 14 11 10 9 9 15 11 10 7 11 12 10 9 10 0 26 25 36 36 32 33 20 22 19 26 37 30 16 26 37 34 21 14 26 37 34 21 13 26 36 28 29 22 26 37 31 25 17 26 36 32 25 17 26 36 33 25 17 26 37 33 25 18 19 23 18 26 36 33 ...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 350 queries.
Test #7:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
50 1 3 1 4 3 1 1 1 1 3 1 1 1 1 3 5 1 1 1 1 3 2 5 1 2 1 4 1 2 3 4 3 3 2 3 1 1 1 1 3 2 2 1 3 4 2 4 2 3 2 0 17 17 16 17 19 19 9 9 7 7 2 6 6 4 5 18 15 11 14 7 9 4 6 4 4 6 4 5 17 16 19 10 12 12 4 5 8 8 6 3 3 2 2 17 13 19 10 9 3 18 17 11 7 4 2 16 16 15 18 18 13 14 11 11 6 7 5 5 3 17 16 19 10 12 4 2 5 5 4 ...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 519 queries.
Test #8:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
50 2 14 8 8 7 12 12 8 8 9 9 10 8 8 4 8 9 9 9 11 13 11 8 7 9 12 7 5 6 4 7 8 10 5 5 10 8 4 10 9 11 7 10 8 6 8 10 7 5 9 0 24 25 30 31 32 33 23 24 15 26 31 31 16 26 31 31 19 10 18 20 26 32 33 21 10 26 32 32 24 9 23 17 26 30 31 26 14 25 23 26 31 30 28 14 27 22 26 32 32 26 10 25 19 26 31 32 25 10 24 19 26...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 427 queries.
Test #9:
score: 0
Accepted
time: 4ms
memory: 3992kb
input:
50 3 1 1 1 2 1 1 1 1 5 1 2 1 1 1 1 3 1 1 2 1 1 1 2 2 1 1 1 1 3 1 2 1 1 2 3 1 2 3 2 1 3 1 2 3 1 2 2 1 1 0 16 15 13 13 6 6 3 4 4 2 3 4 2 15 13 5 8 8 4 4 2 5 5 2 5 15 12 10 10 6 7 7 7 4 5 5 5 1 16 14 7 5 15 13 6 5 3 14 16 15 11 10 7 7 3 3 1 15 12 10 7 7 5 5 2 4 4 3 2 16 14 5 6 10 9 6 5 2 2 4 15 13 6 9 ...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 538 queries.
Test #10:
score: 0
Accepted
time: 0ms
memory: 4196kb
input:
100 1 2 1 1 1 1 1 1 3 3 1 1 2 3 4 1 2 2 2 1 2 2 1 2 2 1 1 1 3 2 1 2 2 1 4 1 1 1 3 2 4 1 3 2 3 3 3 1 1 1 1 2 1 2 2 4 3 1 2 1 1 1 1 3 3 3 2 1 1 2 1 2 2 3 2 1 5 3 5 1 1 1 1 1 1 1 1 3 4 1 2 1 2 1 1 2 1 3 2 1 0 29 30 31 30 26 25 14 13 10 11 7 6 4 5 3 2 2 2 1 0 30 25 25 14 16 18 18 13 15 8 8 5 5 1 31 26 1...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 1219 queries.
Test #11:
score: 0
Accepted
time: 7ms
memory: 4256kb
input:
100 11 13 9 11 8 7 15 12 8 8 7 6 9 12 11 9 10 9 11 16 10 8 9 8 10 6 8 9 13 10 9 7 5 11 14 6 11 16 7 7 8 8 11 8 13 15 11 12 11 11 11 9 10 12 10 6 11 10 5 13 9 9 6 6 6 12 7 12 10 10 9 11 7 11 5 6 9 6 5 9 5 16 11 13 13 10 5 5 8 8 12 11 5 8 8 10 8 10 8 10 0 50 49 65 65 60 61 46 48 27 33 23 50 65 59 42 2...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 859 queries.
Test #12:
score: 0
Accepted
time: 6ms
memory: 4176kb
input:
100 5 3 3 4 2 2 2 8 4 5 4 4 2 2 3 4 6 5 1 4 3 3 2 5 5 2 2 4 3 4 4 4 4 1 3 5 3 4 4 3 3 4 1 3 3 2 5 5 5 1 3 4 3 4 2 2 4 2 1 3 3 7 3 5 5 6 6 1 3 2 3 3 3 2 1 6 3 5 5 3 4 4 2 2 1 5 7 3 3 1 6 2 2 5 2 5 3 3 6 4 0 36 36 47 47 29 32 16 19 10 14 8 7 11 8 8 37 47 31 16 22 23 17 20 10 11 7 6 7 5 37 47 31 16 23 ...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 1100 queries.
Test #13:
score: 0
Accepted
time: 10ms
memory: 4124kb
input:
100 1 1 1 3 1 1 3 1 4 1 2 3 4 1 1 2 4 1 3 2 1 3 2 4 1 3 1 1 2 1 1 1 3 1 1 4 1 1 1 1 4 1 2 1 3 3 1 1 3 4 1 2 2 3 3 1 1 1 1 4 1 1 1 1 1 2 2 2 2 1 2 2 2 2 2 1 1 2 5 1 2 2 1 1 2 2 2 4 1 1 1 5 4 1 3 1 1 1 2 1 0 34 33 37 38 29 28 14 14 7 8 10 10 5 5 2 4 4 3 32 31 30 29 29 16 16 10 11 9 9 3 4 6 6 4 32 30 3...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 1194 queries.
Test #14:
score: 0
Accepted
time: 14ms
memory: 4132kb
input:
100 1 1 2 3 1 3 2 1 1 1 1 1 1 4 1 1 1 2 1 1 2 3 1 1 1 2 1 2 2 2 1 2 1 1 1 4 3 1 1 1 1 2 2 3 2 1 1 1 1 1 1 1 1 5 3 1 1 2 1 1 2 1 2 2 1 2 3 1 1 1 1 1 3 1 1 1 1 1 3 1 1 1 2 2 1 3 3 2 1 4 3 1 2 3 1 1 2 1 2 1 0 30 31 30 29 26 25 14 13 9 8 3 4 9 8 6 4 3 4 0 32 26 27 27 26 19 20 16 15 8 9 10 9 6 7 4 3 2 3 ...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 1218 queries.
Test #15:
score: -100
Wrong Answer
time: 14ms
memory: 4896kb
input:
150 4 2 3 2 2 3 2 4 3 3 4 2 2 4 6 1 3 2 3 5 3 4 4 3 6 3 1 2 4 5 5 3 2 3 3 2 3 1 2 4 2 4 4 1 2 3 2 3 1 1 4 4 3 2 2 1 3 3 1 2 1 6 1 3 2 4 1 4 2 1 4 3 4 1 3 4 2 4 2 5 3 4 2 6 6 2 2 2 3 2 4 4 4 2 2 1 2 1 3 2 3 7 2 1 3 2 5 4 1 2 3 2 3 2 3 5 3 4 5 2 3 1 3 1 2 3 1 3 1 2 3 3 2 3 7 1 2 1 4 2 2 2 3 4 4 3 6 3 ...
output:
? 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer Wrong answer.