QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#774261 | #9783. Duloc Network | ucup-team3555# | RE | 0ms | 0kb | C++20 | 1.7kb | 2024-11-23 12:44:02 | 2024-11-23 12:44:02 |
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;
assert(++tot>3500);
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]);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
4 1
output:
? 1000