QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#774296#9783. Duloc Networkucup-team3555#WA 13ms4892kbC++201.7kb2024-11-23 12:53:552024-11-23 12:53:55

Judging History

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

  • [2024-11-23 12:53:55]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:4892kb
  • [2024-11-23 12:53:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=203;
int n,f[N],ans[N];
map<vector<int>,int>mp;
void NB(int x){cout<<"! "<<x<<endl;exit(0);}
int F(int x){return f[x]==x?x:f[x]=F(f[x]);}
bool Chk()
{
	for(int i=1;i<=n;i++)if(F(i)==F(1))return 0;
	return 1;
}
int Ask(vector<int>v)
{
	vector<int>vis(n+1,0);
	for(int x:v)vis[x]=1;
	if(mp.count(vis))return mp[vis];
	cout<<"? ";
	for(int i=1;i<=n;i++)cout<<vis[i];
	cout<<endl;
	int s;cin>>s;return mp[vis]=s;
}
void Mer(int x,int y)
{
	x=F(x);y=F(y);
	if(x==y)return;
	vector<int>ask;ans[y]=0;f[F(y)]=F(x);
	for(int i=1;i<=n;i++)if(F(i)==F(x))ask.push_back(i);
	ans[x]=Ask(ask);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)f[i]=i,ans[i]=Ask({i});
	while(1)
	{
		vector<int>ve;int sz=0,all=0;
		for(int i=1;i<=n;i++)if(F(i)==i)ve.push_back(i),sz++,all+=ans[i];
		if(sz==1)NB(1);
		int s=Ask(ve);
		if(s==all)NB(0);
		vector<array<int,2>>nb;
		for(int i=0;i<sz;i++)
		{
			vector<int>v;
			for(int j=0;j<sz;j++)if(j!=i)v.push_back(ve[j]);
			while(v.size()>1)
			{
				int mid=v.size()/2,sum=0;vector<int>ask;
				for(int j=0;j<mid;j++)ask.push_back(v[j]),sum+=ans[v[j]];
				sum+=ans[ve[i]];
				ll v0=Ask(ask);
				ask.push_back(ve[i]);
				ll v1=Ask(ask);
				ask.pop_back(); 
				if(v0+ans[ve[i]]>v1){v=ask;continue;}
				ask.clear();sum=0;
				for(int j=mid;j<(int)v.size();j++)ask.push_back(v[j]),sum+=ans[v[j]];
				sum+=ans[ve[i]];
				v0=Ask(ask);
				ask.push_back(ve[i]);
				v1=Ask(ask);
				ask.pop_back();
				if(v0+ans[ve[i]]>v1){v=ask;continue;}
				NB(0);
			}
			if(Ask({ve[i],v[0]})<ans[ve[i]]+ans[v[0]])nb.push_back({ve[i],v[0]});
                        else NB(0);
		}
		for(auto t:nb)Mer(t[0],t[1]);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3636kb

input:

4
1
3
2
2
0
2
2
2
1

output:

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

result:

ok Correct answer with 9 queries.

Test #2:

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

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: 3596kb

input:

4
1
3
2
2
0
2
2
2
1

output:

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

result:

ok Correct answer with 9 queries.

Test #4:

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

input:

2
0
0
0

output:

? 10
? 01
? 11
! 0

result:

ok Correct answer with 3 queries.

Test #5:

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

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

output:

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

result:

ok Correct answer with 514 queries.

Test #6:

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

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
0
26
25
36
36
32
33
20
22
19
26
37
30
16
26
37
34
21
14
26
37
34
21
13
26
36
28
29
22
26
37
31
25
17
26
36
32
25
17
26
36
33
25
17
26
37
33
25
18
19
23
18
26
36
33
...

output:

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

result:

ok Correct answer with 350 queries.

Test #7:

score: 0
Accepted
time: 5ms
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
0
17
17
16
17
19
19
9
9
7
7
2
6
6
4
5
18
15
11
14
7
9
4
6
4
4
6
4
5
17
16
19
10
12
12
4
5
8
8
6
3
3
2
2
17
13
19
10
9
3
18
17
11
7
4
2
16
16
15
18
18
13
14
11
11
6
7
5
5
3
17
16
19
10
12
4
2
5
5
4
...

output:

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

result:

ok Correct answer with 519 queries.

Test #8:

score: 0
Accepted
time: 4ms
memory: 3732kb

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
0
24
25
30
31
32
33
23
24
15
26
31
31
16
26
31
31
19
10
18
20
26
32
33
21
10
26
32
32
24
9
23
17
26
30
31
26
14
25
23
26
31
30
28
14
27
22
26
32
32
26
10
25
19
26
31
32
25
10
24
19
26...

output:

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

result:

ok Correct answer with 427 queries.

Test #9:

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

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

output:

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

result:

ok Correct answer with 538 queries.

Test #10:

score: 0
Accepted
time: 5ms
memory: 4232kb

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
0
29
30
31
30
26
25
14
13
10
11
7
6
4
5
3
2
2
2
1
0
30
25
25
14
16
18
18
13
15
8
8
5
5
1
31
26
1...

output:

? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 1219 queries.

Test #11:

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

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
0
50
49
65
65
60
61
46
48
27
33
23
50
65
59
42
2...

output:

? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 859 queries.

Test #12:

score: 0
Accepted
time: 12ms
memory: 4080kb

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
0
36
36
47
47
29
32
16
19
10
14
8
7
11
8
8
37
47
31
16
22
23
17
20
10
11
7
6
7
5
37
47
31
16
23
...

output:

? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 1100 queries.

Test #13:

score: 0
Accepted
time: 5ms
memory: 4184kb

input:

100
1
1
1
3
1
1
3
1
4
1
2
3
4
1
1
2
4
1
3
2
1
3
2
4
1
3
1
1
2
1
1
1
3
1
1
4
1
1
1
1
4
1
2
1
3
3
1
1
3
4
1
2
2
3
3
1
1
1
1
4
1
1
1
1
1
2
2
2
2
1
2
2
2
2
2
1
1
2
5
1
2
2
1
1
2
2
2
4
1
1
1
5
4
1
3
1
1
1
2
1
0
34
33
37
38
29
28
14
14
7
8
10
10
5
5
2
4
4
3
32
31
30
29
29
16
16
10
11
9
9
3
4
6
6
4
32
30
3...

output:

? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 1194 queries.

Test #14:

score: 0
Accepted
time: 13ms
memory: 4200kb

input:

100
1
1
2
3
1
3
2
1
1
1
1
1
1
4
1
1
1
2
1
1
2
3
1
1
1
2
1
2
2
2
1
2
1
1
1
4
3
1
1
1
1
2
2
3
2
1
1
1
1
1
1
1
1
5
3
1
1
2
1
1
2
1
2
2
1
2
3
1
1
1
1
1
3
1
1
1
1
1
3
1
1
1
2
2
1
3
3
2
1
4
3
1
2
3
1
1
2
1
2
1
0
30
31
30
29
26
25
14
13
9
8
3
4
9
8
6
4
3
4
0
32
26
27
27
26
19
20
16
15
8
9
10
9
6
7
4
3
2
3
...

output:

? 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 00100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok Correct answer with 1218 queries.

Test #15:

score: -100
Wrong Answer
time: 10ms
memory: 4892kb

input:

150
4
2
3
2
2
3
2
4
3
3
4
2
2
4
6
1
3
2
3
5
3
4
4
3
6
3
1
2
4
5
5
3
2
3
3
2
3
1
2
4
2
4
4
1
2
3
2
3
1
1
4
4
3
2
2
1
3
3
1
2
1
6
1
3
2
4
1
4
2
1
4
3
4
1
3
4
2
4
2
5
3
4
2
6
6
2
2
2
3
2
4
4
4
2
2
1
2
1
3
2
3
7
2
1
3
2
5
4
1
2
3
2
3
2
3
5
3
4
5
2
3
1
3
1
2
3
1
3
1
2
3
3
2
3
7
1
2
1
4
2
2
2
3
4
4
3
6
3
...

output:

? 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
? 0100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

wrong answer Wrong answer.