QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#776008 | #9783. Duloc Network | ucup-team5697# | RE | 0ms | 0kb | C++20 | 4.7kb | 2024-11-23 17:17:42 | 2024-11-23 17:17:43 |
answer
#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 i=1;i<=n;i++)
{
if(vis[i]){
res+=deg[i];
}
}
// printf("real %d\n",res>>1);
if(res&1){
assert(false);
}
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: 0
Runtime Error
input:
4 1 3 2 2 2
output:
? 1000 ? 0100 ? 0010 ? 0001 ? 0110