QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#775923#9783. Duloc Networkucup-team5697#WA 2ms4036kbC++234.8kb2024-11-23 17:03:432024-11-23 17:03:43

Judging History

你现在查看的是最新测评结果

  • [2024-11-23 17:03:43]
  • 评测
  • 测评结果：WA
  • 用时：2ms
  • 内存：4036kb
查看
  • [2024-11-23 17:03:43]
  • 提交

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",&deg[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;
}
源文件, 语言: C++23

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3692kb

input:

4
1
3
2
2
1
2
2
1
1
0

output:

? 1000
? 0100
? 0010
? 0001
? 1110
? 1100
? 1100
? 1110
? 1110
? 1111
! 1

result:

ok Correct answer with 10 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: 0ms
memory: 3752kb

input:

4
1
3
2
2
1
2
2
1
1
0

output:

? 1000
? 0100
? 0010
? 0001
? 1110
? 1100
? 1100
? 1110
? 1110
? 1111
! 1

result:

ok Correct answer with 10 queries.

Test #4:

score: 0
Accepted
time: 1ms
memory: 3752kb

input:

2
0
0
0

output:

? 10
? 01
? 11
! 0

result:

ok Correct answer with 3 queries.

Test #5:

score: 0
Accepted
time: 1ms
memory: 3776kb

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
14
16
17
14
12
10
10
5
4
2
2
14
16
17
14
12
8
7
6
5
5
4
4
3
3
3
14
15
16
16
12
11
7
9
6
5
5
5
13
15
17
15
15
12
11
8
6
6
5
3
6

output:

? 10000000000000000000000000000000000000000000000000
? 01000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000
? 00010000000000000000000000000000000000000000000000
? 00001000000000000000000000000000000000000000000000
? 000001000000000000000000000000000...

result:

ok Correct answer with 101 queries.

Test #6:

score: 0
Accepted
time: 0ms
memory: 3772kb

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
16
27
33
34
34
32
22
21
19
19
16
27
33
34
34
32
30
22
21
21
16
26
32
35
35
33
32
30
22
22
15
25
31
36
35
34
33
32
30
30
15
25
31
35
34
35
34
33
32
32
15
25
31
34
35...

output:

? 10000000000000000000000000000000000000000000000000
? 01000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000
? 00010000000000000000000000000000000000000000000000
? 00001000000000000000000000000000000000000000000000
? 000001000000000000000000000000000...

result:

ok Correct answer with 423 queries.

Test #7:

score: 0
Accepted
time: 1ms
memory: 3696kb

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
14
16
16
15
13
13
9
9
4
5
3
2
14
16
16
15
13
11
7
8
3
4
3
1
14
17
15
16
12
9
8
5
4
6
2
13
17
16
16
12
12
7
7
6
6
2

output:

? 10000000000000000000000000000000000000000000000000
? 01000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000
? 00010000000000000000000000000000000000000000000000
? 00001000000000000000000000000000000000000000000000
? 000001000000000000000000000000000...

result:

ok Correct answer with 96 queries.

Test #8:

score: 0
Accepted
time: 0ms
memory: 4032kb

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
16
27
31
32
33
30
24
21
15
20
20
16
27
31
32
33
30
27
24
21
23
23
16
26
31
32
33
33
30
27
24
24
15
25
31
31
33
33
33
30
27
27
15
25
31
30
32
33
33
33
30
30
15
25
31
31
32
33
33
33
33
...

output:

? 10000000000000000000000000000000000000000000000000
? 01000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000
? 00010000000000000000000000000000000000000000000000
? 00001000000000000000000000000000000000000000000000
? 000001000000000000000000000000000...

result:

ok Correct answer with 425 queries.

Test #9:

score: 0
Accepted
time: 0ms
memory: 4000kb

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
12
15
15
10
7
5
4
5
3
2
12
15
15
10
7
5
4
4
4
2
12
14
14
12
8
9
6
4
5
3
4
2
5
4
11
15
15
13
9
6
7
6
4
4
4
2

output:

? 10000000000000000000000000000000000000000000000000
? 01000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000
? 00010000000000000000000000000000000000000000000000
? 00001000000000000000000000000000000000000000000000
? 000001000000000000000000000000000...

result:

ok Correct answer with 96 queries.

Test #10:

score: 0
Accepted
time: 2ms
memory: 3716kb

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
26
31
28
22
16
13
6
6
3
4
2
3
1
2
0
0
26
31
29
24
19
14
16
10
15
10
9
5
4
4
3
3
3
25
32
28
24
20...

output:

? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 222 queries.

Test #11:

score: 0
Accepted
time: 0ms
memory: 3804kb

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
32
54
66
67
63
55
48
40
33
27
23
19
19
32
54
65
...

output:

? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 1017 queries.

Test #12:

score: -100
Wrong Answer
time: 1ms
memory: 4036kb

input:

100
5
3
3
4
2
2
2
8
4
5
4
4
2
2
3
4
6
5
1
4
3
3
2
5
5
2
2
4
3
4
4
4
4
1
3
5
3
4
4
3
3
4
1
3
3
2
5
5
5
1
3
4
3
4
2
2
4
2
1
3
3
7
3
5
5
6
6
1
3
2
3
3
3
2
1
6
3
5
5
3
4
4
2
2
1
5
7
3
3
1
6
2
2
5
2
5
3
3
6
4
28
38
45
39
32
29
19
16
13
10
7
6

output:

? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

wrong answer Wrong answer.
English 繁體中文 简体中文

伺服器時間: 2025-01-21 01:55:34 | 開源專案