QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#774009 | #9783. Duloc Network | ucup-team5319# | WA | 1ms | 3588kb | C++14 | 3.0kb | 2024-11-23 11:15:03 | 2024-11-23 11:15:03 |
Judging History
answer
//Linkwish's code
#include<bits/stdc++.h>
//#define endl '\n'
#define si inline
#define fi first
#define se second
using namespace std;
typedef long long ll;typedef __int128 li;typedef long double ld;
typedef pair<int,int> pii;typedef pair<ll,ll> pll;
typedef const int ci;typedef const ll cl;ci iinf=INT_MAX;cl linf=LLONG_MAX;
template<typename T>si bool gmax(T &x,const T y){if(x<y)return x=y,1;return 0;}
template<typename T>si bool gmin(T &x,const T y){if(y<x)return x=y,1;return 0;}
namespace LinkWish{
ci N=205;
int n;
int bl[N];
vector<int> p[N];
int d[N];
bool e[N][N];
bool onp[N],got[N];
int tms;
si void add(int x,int y){
e[x][y]=e[y][x]=true;
//cout<<x<<' '<<y<<endl;
}
si int ask(vector<int> x){
//tms++;
//memset(got,0,sizeof got);
//memset(onp,0,sizeof onp);
//for(int i:x)onp[i]=true;
//for(int i:x){
// for(int j=1;j<=n;j++){
// if(e[i][j]&&!onp[j])got[j]=true;
// }
//}
vector<int> s(n,0);
for(int i:x)s[i-1]=1;
for(int i:s)cout<<i;
cout<<endl;
//int res=0;
//for(int i=1;i<=n;i++)if(got[i])res++;
//cout<<res<<endl;
//return res;
int res;cin>>res;
return res;
}
si int ask(int x,int y){
vector<int> que=p[x];
for(int i:p[y])que.push_back(i);
return ask(que);
}
si void merge(int x,int y){for(int i:p[y])p[x].push_back(i),bl[i]=x;}
void mian(){
cin>>n;
//vector<int> seq(n);
//iota(seq.begin(),seq.end(),1);
//mt19937 R(time(0));
//shuffle(seq.begin(),seq.end(),R);
////for(int i=1;i<n;i++)add(i,i+1);
//for(int i=0;i<n-1;i++)add(seq[i],seq[i+1]);
priority_queue<pii> q;
for(int i=1;i<=n;i++){
d[i]=ask(vector<int>{i}),bl[i]=i,p[i].push_back(i);
q.emplace(d[i],i);
}
static bool vis[N];
for(;!q.empty();q.pop()){
int id=q.top().se,nv=q.top().fi;
q.pop();
if(nv!=d[id]||bl[id]!=id)continue;
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++){
if(!vis[bl[i]]&&bl[i]!=id){
int x=bl[i];
vis[x]=true;
//cout<<"ASKCON "<<id<<' '<<x<<endl;
int v=ask(id,x);
if(v!=d[id]+d[x])merge(id,x),d[id]=v;
}
}
if(d[id]==0){
if((int)p[id].size()!=n)cout<<"! 0"<<endl;
else cout<<"! 1"<<endl;
return ;
}
memset(vis,0,sizeof vis);
for(int i=n;i;i--){
if(!vis[bl[i]]&&bl[i]!=id){
int x=bl[i];
vis[x]=true;
//cout<<"ASKCON "<<id<<' '<<x<<endl;
int v=ask(id,x);
if(v!=d[id]+d[x])merge(id,x),d[id]=v;
}
}
//cout<<"DONE "<<id<<endl;
//for(int i:p[id])cout<<i<<' ';
//cout<<endl;
//cout<<endl;
if(d[id]==0){
if((int)p[id].size()!=n)cout<<"! 0"<<endl;
else cout<<"! 1"<<endl;
return ;
}
q.emplace(d[id],id);
}
assert(0);
}
}
signed main(){
//#ifndef ONLINE_JUDGE
//assert(freopen("in.in","r",stdin));
//assert(freopen("out.out","w",stdout));
//#endif
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
LinkWish::mian();
//cerr<<"DONEIN "<<LinkWish::tms<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3588kb
input:
4
output:
1000
result:
wrong answer format Expected '!' or '?', but found '1000'