QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#773856 | #9783. Duloc Network | ucup-team5318# | WA | 1ms | 3928kb | C++14 | 3.1kb | 2024-11-23 10:35:28 | 2024-11-23 10:35:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define pb emplace_back
#define mp make_pair
#define fi first
#define se second
using vi=vector<int>;
using pi=pair<int,int>;
int n;
map<vi,int> mem;
vector<vi> G;
int ask(const vi &S){
if(mem.count(S)){
return mem[S];
}
assert(mem.size()<=3500);
int cnt=0;
cout<<"? ";
rep(i,1,n){
cout<<S[i];
cnt+= S[i];
}
cout<<endl;
int get; cin>>get;
//int get=0;
//rep(u,1,n){
// if(S[u]==0){
// bool ok=0;
// for(int v:G[u]){
// if(S[v]){
// ok=1;
// }
// }
// get+= ok;
// }
//}
return mem[S]=get+cnt;
}
bool chc(const vi &A,const vi &B){
vi C(n+1);
rep(i,1,n){
assert(A[i]+B[i]<2);
C[i]=A[i]|B[i];
}
return ask(A)+ask(B)!=ask(C);
}
struct dsu{
vi fa;
dsu(int n){
fa.resize(n);
fill(fa.begin(), fa.end(), -1);
}
int find(int d){
return fa[d]<0? d: fa[d]=find(fa[d]);
}
void merge(int u,int v){
if((u=find(u))==(v=find(v))){
return;
}
fa[find(u)]=find(v);
}
};
bool chk(const vector<vi> &S){
//cout<<"!"<<S.size()<<endl;
//for(auto x:S){
// for(int y:x){
// cout<< y <<' ';
// }
// cout<<endl;
//}
if(S.size()==1){
return 1;
}
vector<vi> pre(S.size()+1), suf(S.size()+1);
pre[0].resize(n+1);
suf[S.size()].resize(n+1);
rep(i,0,(int)S.size()-1){
pre[i+1]=pre[i];
for(int u:S[i]){
pre[i+1][u]=1;
}
}
per(i,(int)S.size()-1,0){
suf[i]=suf[i+1];
for(int u:S[i]){
suf[i][u]=1;
}
}
auto qry=[&](int pos){
vi st(n+1);
for(int u:S[pos]){
st[u]=1;
}
auto qpre=[&](int pos){
if(!chc(st, pre[pos])){
return -1;
}
int l=1, r=pos;
while(l<r){
int mid=(l+r)/2;
if(chc(st, pre[mid])){
r=mid;
}
else{
l=mid+1;
}
}
return l;
};
auto qsuf=[&](int pos){
if(!chc(st, suf[pos+1])){
return -1;
}
int l=pos+1, r=(int)S.size()-1;
while(l<r){
int mid=(l+r+1)/2;
if(chc(st, suf[mid])){
l=mid;
}
else{
r=mid-1;
}
}
return l;
};
int get=qpre(pos);
if(get!=-1){
return get;
}
return qsuf(pos);
};
vector<vi> tmp(S.size());
dsu bel(S.size());
rep(i,0,(int)S.size()-1){
int get=qry(i);
if(get==-1){
return false;
}
bel.merge(i, get);
}
rep(i,0,(int)S.size()-1){
tmp[bel.find(i)].insert(tmp[bel.find(i)].end(), S[i].begin(), S[i].end());
}
for(auto it=tmp.begin(); it!=tmp.end(); ){
if((*it).empty()){
it=tmp.erase(it);
}
else{
it++;
}
}
return chk(tmp);
}
mt19937 rnd(time(0));
signed main(){
#ifndef ONLINE_JUDGE
//assert(freopen(".in","r",stdin));
//assert(freopen(".out","w",stdout));
#endif
ios::sync_with_stdio(0);cin.tie(0);
cin>>n;
vector<vi> S;
rep(i,1,n){
S.pb((vi){i});
}
G.resize(n+1);
rep(i,2,n){
G[i/2].pb(i);
G[i].pb(i/2);
}
bool ans=chk(S);
cout<<"! "<<ans<<endl;
//cerr<<mem.size()<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3700kb
input:
4 1 0 1 0 1 1 2 2 3 2 2 1 2 1
output:
? 1000 ? 0000 ? 0111 ? 1111 ? 0011 ? 1011 ? 0001 ? 1001 ? 0100 ? 1100 ? 0010 ? 1110 ? 1010 ? 1101 ! 1
result:
ok Correct answer with 14 queries.
Test #2:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
2 0 0 0 0
output:
? 10 ? 00 ? 01 ? 11 ! 0
result:
ok Correct answer with 4 queries.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
4 1 0 1 0 1 1 2 2 3 2 2 1 2 1
output:
? 1000 ? 0000 ? 0111 ? 1111 ? 0011 ? 1011 ? 0001 ? 1001 ? 0100 ? 1100 ? 0010 ? 1110 ? 1010 ? 1101 ! 1
result:
ok Correct answer with 14 queries.
Test #4:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
2 0 0 0 0
output:
? 10 ? 00 ? 01 ? 11 ! 0
result:
ok Correct answer with 4 queries.
Test #5:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
50 3 0 1 0 19 18 19 19 16 17 9 11 5 7 3 5 1 4 2 18 18 17 18 18 18 18 18 18 19 1 5 3 17 16 13 14 16 15 16 15 15 1 6 4 15 14 16 12 8 8 6 1 7 5 15 17 14 17 18 18 17 17 4 10 9 9 3 11 6 5 6 1 12 7 6 15 16 15 14 18 18 19 18 18 19 1 13 8 16 16 15 17 17 16 2 14 9 12 11 3 14 10 14 13 12 3 16 13 15 14 14 2 15...
output:
? 10000000000000000000000000000000000000000000000000 ? 00000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111 ? 11111111111111111111111111111111111111111111111111 ? 00000000000000000000000001111111111111111111111111 ? 100000000000000000000000011111111...
result:
ok Correct answer with 383 queries.
Test #6:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
50 10 0 1 0 25 24 35 34 37 36 29 31 18 25 10 17 13 19 8 21 14 6 22 21 13 13 30 29 22 8 32 25 25 17 10 33 25 24 17 8 34 26 24 17 8 35 25 24 18 8 35 32 26 24 17 9 34 30 22 21 17 13 35 35 28 26 18 15 36 36 30 28 22 11 35 33 27 25 18 9 34 34 26 25 18 10 33 33 25 22 16 14 32 36 27 26 20 6 31 35 31 24 22 ...
output:
? 10000000000000000000000000000000000000000000000000 ? 00000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111 ? 11111111111111111111111111111111111111111111111111 ? 00000000000000000000000001111111111111111111111111 ? 100000000000000000000000011111111...
result:
ok Correct answer with 342 queries.
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 3852kb
input:
50 1 0 1 0 16 15 20 19 15 16 19 18 17 18 3 4 2 16 15 20 19 14 13 7 9 5 7 2 4 1 5 3 15 21 19 18 20 21 18 19 4 9 4 17 18 21 15 8 7 4 3 12 5 18 21 17 18 15 18 1 13 6 16 15 19 18 15 16 14 14 1 14 7 15 18 13 8 12 12 10 11 1 13 10 12 11 1 12 10 12 11 3 14 14 7 6 4 1 15 9 8 17 17 19 13 16 17 1 16 10 18 19 ...
output:
? 10000000000000000000000000000000000000000000000000 ? 00000000000000000000000000000000000000000000000000 ? 01111111111111111111111111111111111111111111111111 ? 11111111111111111111111111111111111111111111111111 ? 00000000000000000000000001111111111111111111111111 ? 100000000000000000000000011111111...
result:
wrong answer Wrong answer.