QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#774288 | #9783. Duloc Network | ucup-team3555# | TL | 1ms | 3852kb | C++20 | 1.2kb | 2024-11-23 12:52:38 | 2024-11-23 12:52:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=203;
int n,tot,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;
if(++tot>=3500)assert(0);
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++)
{
for(int j=0;j<sz;j++)if(j!=i&&Ask({ve[i],ve[j]})<ans[ve[i]]+ans[ve[j]])
nb.push_back({ve[i],ve[j]});
}
for(auto t:nb)Mer(t[0],t[1]);
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3608kb
input:
4 1 3 2 2 0 2 2 2 2 2 1 1
output:
? 1000 ? 0100 ? 0010 ? 0001 ? 1111 ? 1100 ? 1010 ? 1001 ? 0110 ? 0101 ? 0011 ? 1110 ! 1
result:
ok Correct answer with 12 queries.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3852kb
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: 3776kb
input:
4 1 3 2 2 0 2 2 2 2 2 1 1
output:
? 1000 ? 0100 ? 0010 ? 0001 ? 1111 ? 1100 ? 1010 ? 1001 ? 0110 ? 0101 ? 0011 ? 1110 ! 1
result:
ok Correct answer with 12 queries.
Test #4:
score: 0
Accepted
time: 0ms
memory: 3488kb
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 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 4 4 4 4 7 6 4 4 5 6 6 3 4 5 7 6 4 4 4 5 7 4 6 4 7 6 4 4 5 5 5 5 4 4 5 4 5 7 4 4 4 5 6 8 4 4 6 5 5 2 2 2 5 2 2 2 3 4 4 3 1 3 5 4 2 2 2 3 5 2 4 2 5 4 3 3 3 5 3 3 2 2 2 2 3 5 2 2 4 4 4 7 3 2 4 3 4 2...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...