QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#775929 | #9783. Duloc Network | ucup-team5697# | WA | 2ms | 4024kb | C++23 | 4.8kb | 2024-11-23 17:04:28 | 2024-11-23 17:04:29 |
Judging History
answer
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<string>
#include<bitset>
#include<numeric>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=205;
const int N=200;
const int INF=0x3f3f3f3f;
const long long LINF=0x3f3f3f3f3f3f3f3f;
int n,k,cnt=0;
int deg[MAXN];
basic_string <int> s[MAXN];
int v[MAXN];
bool vis[MAXN];
namespace Q{
bool con=true;
int cnt=0;
int n,m;
bool e[MAXN][MAXN];
char s[MAXN];
int pre[MAXN];
inline int find(int x){
return pre[x]^x?pre[x]=find(pre[x]):x;
}
inline void start(){
scanf("%d%d",&n,&m);
iota(pre+1,pre+1+n,1);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
e[x][y]=e[y][x]=1;
pre[find(x)]=find(y);
}
for(int i=1;i<=n;i++)
{
if(find(i)!=find(1)){
con=false;
// fputs("answer is disconnected!\n",stderr);
return ;
}
}
// fputs("answer is connected!\n",stderr);
}
inline int qry(){
cnt++;
printf("%s\n",s+1);
int res=0;
for(int i=1;i<=n;i++)
{
if(s[i]=='1'){
continue;
}
for(int j=1;j<=n;j++)
{
if(e[i][j]&&s[j]=='1'){
res++;
}
}
}
printf("%d\n",res);
return res;
}
}
#include<cassert>
int qcnt=0;
inline int query(basic_string <int> qry){
qcnt++;
if(qcnt>3500){
assert(false);
}
memset(vis,false,sizeof(bool)*(n+1));
for(int x:qry)
{
vis[x]=true;
}
putchar('?');
putchar(' ');
for(int i=1;i<=n;i++)
{
putchar(vis[i]+'0');
#ifdef LOCAL
Q::s[i]=vis[i]+'0';
#endif
}
putchar('\n');
fflush(stdout);
int res;
#ifdef LOCAL
res=Q::qry();
#else
scanf("%d",&res);
#endif
// printf("!%d\n",res);
res=-res;
for(int x:qry)
{
res+=deg[x];
}
// printf("real %d\n",res>>1);
return res>>1;
}
// #define DEBUGER
void divide(int l,int r){
if(l+1==r){
basic_string <int> qry=s[l]+s[r];
int now=query(qry);
if(now!=v[l]+v[r]){
// puts("join");
// for(int x:s[l])printf("(%d)",x);puts("");
// for(int x:s[r])printf("(%d)",x);puts("");
// printf("inside %d\n",now);
s[l]+=s[r];
s[r].clear();
v[l]=now;
return ;
}
#ifdef DEBUGER
freopen("answ.out","w",stdout);
puts(Q::con?"connected":"disconnected");
#endif
puts("! 0");
fflush(stdout);
#ifdef LOCAL
printf("qry times:%d\n",qcnt);
printf("qry times:%d\n",Q::cnt);
#endif
exit(0);
}
int pl=l+(r-l+1)/3,pr=r-(r-l+1)/3;
basic_string <int> qry;
int sum=0;
if(l<pl-1){
qry.clear();
sum=0;
for(int i=l;i<pl;i++)
{
qry+=s[i];
sum+=v[i];
}
if(query(qry)-sum){
divide(l,pl-1);
return ;
}
}
if(pl<pr){
qry.clear();
sum=0;
for(int i=pl;i<=pr;i++)
{
qry+=s[i];
sum+=v[i];
}
if(query(qry)-sum){
divide(pl,pr);
return ;
}
}
// if(pr+1<r){
// qry.clear();
// sum=0;
// for(int i=r;i>pr;i--)
// {
// qry+=s[i];
// sum+=v[i];
// }
// if(query(qry)-sum){
// divide(pr+1,r);
// return ;
// }
// }
qry.clear();
sum=0;
for(int i=l;i<=pr;i++)
{
qry+=s[i];
sum+=v[i];
}
// puts("calc");
// for(int i=l;i<=r;i++){for(int x:s[i])printf("(%d)",x);puts("");}
if(query(qry)-sum){
// puts("l!!!!!!!!!!!");
divide(l,pr);
return ;
}
qry.clear();
sum=0;
for(int i=pl;i<=r;i++)
{
qry+=s[i];
sum+=v[i];
}
if(query(qry)-sum){
// puts("r!!!!!!!!!!!");
divide(pl,r);
return ;
}
for(int i=pr+1;i<=r;i++)
{
swap(s[i],s[pl+(i-pr-1)]);
swap(v[i],v[pl+(i-pr-1)]);
}
divide(l,l+(pl-l)+(r-pr)-1);
}
inline void calc(){
cnt=0;
for(int i=1;i<=n;i++)
{
if(!s[i].empty()){
cnt++;
s[i].swap(s[cnt]);
swap(v[i],v[cnt]);
}
}
divide(1,cnt);
}
inline void solve(){
#ifdef LOCAL
Q::start();
#endif
scanf("%d",&n);
k=n;
for(int i=1;i<=n;i++)
{
qcnt++;
putchar('?');
putchar(' ');
for(int j=1;j<=n;j++)
{
putchar((i==j)+'0');
#ifdef LOCAL
Q::s[j]=(i==j)+'0';
#endif
}
putchar('\n');
fflush(stdout);
#ifdef LOCAL
deg[i]=Q::qry();
printf("deg[%d]=%d\n",i,deg[i]);
#else
scanf("%d",°[i]);
#endif
s[i].push_back(i);
}
for(int i=1;i<n;i++)
{
calc();
}
#ifdef DEBUGER
freopen("answ.out","w",stdout);
puts(Q::con?"connected":"disconnected");
#endif
puts("! 1");
fflush(stdout);
#ifdef LOCAL
printf("qry times:%d\n",qcnt);
printf("qry times:%d\n",Q::cnt);
#endif
}
signed main(){
#ifdef LOCAL
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
// atexit([](){fprintf(stderr,"%.3lfs\n",(double)clock()/CLOCKS_PER_SEC);});
#endif
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4020kb
input:
4 1 3 2 2 2 2 1 1 0
output:
? 1000 ? 0100 ? 0010 ? 0001 ? 0110 ? 0110 ? 1110 ? 1110 ? 1111 ! 1
result:
ok Correct answer with 9 queries.
Test #2:
score: 0
Accepted
time: 1ms
memory: 3740kb
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: 3728kb
input:
4 1 3 2 2 2 2 1 1 0
output:
? 1000 ? 0100 ? 0010 ? 0001 ? 0110 ? 0110 ? 1110 ? 1110 ? 1111 ! 1
result:
ok Correct answer with 9 queries.
Test #4:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
2 0 0 0
output:
? 10 ? 01 ? 11 ! 0
result:
ok Correct answer with 3 queries.
Test #5:
score: 0
Accepted
time: 0ms
memory: 3616kb
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 17 7 10 7 2 9 5 3 4 4 3 3 3 16 7 12 7 2 9 7 6 8 7 6 5 17 7 13 8 3 11 6 4 9 6 6
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 86 queries.
Test #6:
score: 0
Accepted
time: 2ms
memory: 3988kb
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 33 30 20 19 19 32 32 29 20 20 31 33 31 29 29 31 34 32 31 31 31 35 33 32 32 30 35 34 33 33 30 35 34 34 29 34 34 34 28 35 33 33 28 36 35 35 27 35 36 36 26 34 36 36 26...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 223 queries.
Test #7:
score: 0
Accepted
time: 1ms
memory: 3664kb
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 16 12 7 15 5 8 5 9 4 2 5 3 2 15 11 8 16 5 7 4 8 3 2 4 3 1 16 10 8 17 13 5 5 3 4 6 2 16 10 8 16 5 7 12 12 4 4 7 7 5 6 6 2
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 103 queries.
Test #8:
score: 0
Accepted
time: 0ms
memory: 4024kb
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 31 27 23 20 20 31 30 26 23 23 31 33 29 26 26 31 33 32 29 29 31 33 32 32 32 30 33 32 32 32 30 33 32 32 29 32 32 32 28 32 31 31 28 31 31 31 27 30 30 30 26 31 29 29 26 31 30 30 25 31 30 ...
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 225 queries.
Test #9:
score: 0
Accepted
time: 1ms
memory: 4012kb
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 15 4 3 4 2 5 3 2 14 5 4 4 2 4 4 2 15 6 8 2 6 5 5 4 2 5 4 15 6 8 13 4 6 9 3 3 6 7 4 6 4 4 4 2
output:
? 10000000000000000000000000000000000000000000000000 ? 01000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000 ? 00010000000000000000000000000000000000000000000000 ? 00001000000000000000000000000000000000000000000000 ? 000001000000000000000000000000000...
result:
ok Correct answer with 94 queries.
Test #10:
score: 0
Accepted
time: 2ms
memory: 3724kb
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 30 14 4 3 1 2 0 0 29 15 18 7 3 3 29 14 19 9 7 15 11 4 7 10 8 3 4 7 5 3 5 5 2 32 14 19 9 7 15 11 ...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok Correct answer with 170 queries.
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 3724kb
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 63 57 27 23 19 19 62 58 33 27 27 62 58 40 33 33 ...
output:
? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 ? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
wrong answer Wrong answer.