QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#774308#9783. Duloc Networkucup-team3555#RE 1ms3752kbC++201.2kb2024-11-23 12:56:192024-11-23 12:56:21

Judging History

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

  • [2024-11-23 12:56:21]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3752kb
  • [2024-11-23 12:56:19]
  • 提交

answer

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

typedef long long ll;
const int N=203;
int n,tot,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;
	if(++tot>=3500)assert(0);
	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});
	int tim=0;
	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++)
		{
			for(int j=0;j<sz;j++)if(j!=i&&Ask({ve[i],ve[j]})<ans[ve[i]]+ans[ve[j]])
				nb.push_back({ve[i],ve[j]});
		}
		for(auto t:nb)Mer(t[0],t[1]);
		assert(++tim<=100);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
1
3
2
2
0
2
2
2
2
2
1
1

output:

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

result:

ok Correct answer with 12 queries.

Test #2:

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

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

input:

4
1
3
2
2
0
2
2
2
2
2
1
1

output:

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

result:

ok Correct answer with 12 queries.

Test #4:

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

input:

2
0
0
0

output:

? 10
? 01
? 11
! 0

result:

ok Correct answer with 3 queries.

Test #5:

score: -100
Runtime Error

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
4
4
4
4
7
6
4
4
5
6
6
3
4
5
7
6
4
4
4
5
7
4
6
4
7
6
4
4
5
5
5
5
4
4
5
4
5
7
4
4
4
5
6
8
4
4
6
5
5
2
2
2
5
2
2
2
3
4
4
3
1
3
5
4
2
2
2
3
5
2
4
2
5
4
3
3
3
5
3
3
2
2
2
2
3
5
2
2
4
4
4
7
3
2
4
3
4
2...

output:

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

result: