QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#466052#8871. Interactive ReconstructionPhantomThreshold#AC ✓72ms5708kbC++20972b2024-07-07 15:17:402024-07-07 15:17:40

Judging History

This is the latest submission verdict.

  • [2024-07-07 15:17:40]
  • Judged
  • Verdict: AC
  • Time: 72ms
  • Memory: 5708kb
  • [2024-07-07 15:17:40]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin>>n;
	cout<<"QUERY ";
	for(int i=1;i<=n;i++)cout<<1;
	cout<<endl;
	vector<int> deg(n+5);
	for(int i=1;i<=n;i++)
	{
		cin>>deg[i];
	}
	vector<vector<int>> sum(15,vector<int>(n+5));
	for(int b=0;b<15;b++)
	{
		cout<<"QUERY ";
		for(int i=1;i<=n;i++)
		{
			if((i>>b)&1)cout<<1;
			else cout<<0;
		}
		cout<<endl;
		for(int i=1;i<=n;i++)
			cin>>sum[b][i];
	}
	vector<pair<int,int>> edges;
	queue<int> q;
	for(int i=1;i<=n;i++)
	{
		if(deg[i]==1)
			q.push(i);
	}
	while(not q.empty())
	{
		int u=q.front();q.pop();
		if(deg[u]!=1)continue;
		int v=0;
		for(int b=0;b<15;b++)
			if(sum[b][u])
				v+=(1<<b);
		edges.emplace_back(u,v);
		for(int b=0;b<15;b++)
			if((u>>b)&1)
				sum[b][v]--;
		deg[v]--;
		if(deg[v]==1)q.push(v);
	}
	cout<<"ANSWER"<<endl;
	for(auto [u,v]:edges)
		cout<<u<<' '<<v<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 53ms
memory: 5572kb

input:

30000
1 1 3 3 1 3 1 1 3 1 3 1 1 3 3 3 3 1 3 3 1 3 3 1 3 1 1 1 3 3 3 3 3 1 1 3 3 3 1 3 3 3 1 3 3 3 3 1 1 3 3 1 3 3 3 1 1 1 3 1 1 3 1 1 3 1 3 1 3 1 3 3 3 3 1 3 1 1 1 3 3 1 3 3 3 3 1 3 1 3 1 3 3 3 3 1 1 3 3 1 3 3 3 1 3 3 1 3 3 3 1 1 3 1 1 1 1 1 3 1 3 1 3 1 1 3 3 3 3 3 3 3 1 1 1 3 1 1 3 3 3 1 1 1 3 1 1 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #2:

score: 0
Accepted
time: 31ms
memory: 4672kb

input:

16384
1 3 3 3 3 3 1 1 3 1 3 3 3 3 3 1 1 1 1 3 3 3 3 3 1 1 3 1 1 1 3 3 3 3 1 1 1 3 3 1 3 3 3 3 1 1 1 3 1 3 3 1 3 1 3 1 1 3 1 3 3 1 3 1 1 3 1 3 1 3 3 3 3 1 1 1 1 1 1 1 1 3 3 1 1 1 3 1 3 1 1 3 1 3 1 1 1 1 3 1 1 3 1 1 3 3 3 1 1 3 1 3 1 1 1 1 3 1 1 1 3 3 1 3 1 3 3 1 1 1 3 3 3 1 1 1 1 1 3 1 1 1 3 1 3 1 1 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #3:

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

input:

8
1 3 2 1 3 1 1 2
0 3 1 1 1 0 0 1
1 2 1 0 1 0 1 1
0 1 1 1 1 0 0 2
0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

output:

QUERY 11111111
QUERY 10101010
QUERY 01100110
QUERY 00011110
QUERY 00000001
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
ANSWER
1 2
4 5
6 8
7 2
8 5
2 3
5 3

result:

ok correct answer

Test #4:

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

input:

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

output:

QUERY 1111
QUERY 1010
QUERY 0110
QUERY 0001
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
QUERY 0000
ANSWER
1 4
2 4
3 4

result:

ok correct answer

Test #5:

score: 0
Accepted
time: 66ms
memory: 5568kb

input:

30000
1 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 1 2 2 2 2 2 2 3 2 3 2 2 2 2 4 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 2 2 2 3 2 2 2 2 2 2 2 1 2 2 2 1 3 1 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 1 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 1 2 3 2 3 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #6:

score: 0
Accepted
time: 65ms
memory: 5524kb

input:

29999
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 1 2 2 2 3 2 2 2 2 2 2 2 2 2 3 2 3 2 2 2 2 2 2 2 1 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 1 2 2 2 2 2 1 2 2 2 2 2 2 2 4 2 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 2 3 2 2 2 2 1 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 1 2 2 1 2 2 2 2 2 2 2 2 1 2 1 2 2 2 2 2 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #7:

score: 0
Accepted
time: 59ms
memory: 5552kb

input:

30000
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #8:

score: 0
Accepted
time: 72ms
memory: 5664kb

input:

29997
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #9:

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

input:

8
2 2 2 1 2 2 1 2
0 1 1 1 1 2 0 1
1 1 1 0 1 1 1 1
2 1 2 0 0 0 0 1
0 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

output:

QUERY 11111111
QUERY 10101010
QUERY 01100110
QUERY 00011110
QUERY 00000001
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
ANSWER
4 1
7 2
1 6
2 8
6 3
8 5
3 5

result:

ok correct answer

Test #10:

score: 0
Accepted
time: 68ms
memory: 5696kb

input:

30000
2 2 1 4 10 4 3 1 1 1 1 1 4 1 1 1 2 4 2 3 1 2 4 1 1 3 1 5 1 1 5 3 1 1 2 2 1 4 1 3 3 2 2 2 2 1 1 2 3 4 3 4 1 2 2 3 1 1 1 1 1 1 3 2 1 2 2 1 1 2 1 2 2 2 1 1 3 1 4 1 2 1 3 2 1 2 1 1 1 3 1 7 2 1 2 1 1 6 2 1 5 4 1 1 2 1 1 1 3 1 1 1 1 1 1 4 3 3 2 1 2 1 2 1 1 1 5 1 4 2 1 1 1 1 4 1 1 2 1 7 2 1 1 1 1 1 1...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #11:

score: 0
Accepted
time: 67ms
memory: 5536kb

input:

29999
4 2 3 2 2 1 2 4 3 3 3 1 6 2 1 2 1 2 2 1 1 1 1 3 3 1 2 4 1 1 1 2 4 7 3 1 1 2 1 2 2 1 1 3 5 4 3 1 1 1 1 2 1 2 1 2 3 1 1 4 1 1 7 1 1 1 2 1 1 2 9 3 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 4 2 1 1 3 2 1 2 1 1 1 1 1 1 1 2 1 1 2 4 8 4 3 1 1 5 3 1 3 3 1 5 1 1 5 1 1 1 6 2 2 2 1 2 1 1 1 1 4 1 6 3 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #12:

score: 0
Accepted
time: 71ms
memory: 5536kb

input:

30000
1 4 1 1 2 1 1 1 1 1 2 1 2 1 1 2 1 1 1 3 1 1 1 7 3 2 5 1 1 9 1 1 4 1 1 4 2 1 2 1 1 1 3 3 1 1 1 1 2 4 4 6 1 2 2 1 1 1 2 2 2 1 2 1 3 3 3 2 1 1 1 1 1 1 1 4 2 1 2 1 1 2 1 3 5 1 1 2 2 1 2 3 1 3 1 1 1 2 1 2 2 1 1 1 1 1 3 2 1 1 1 1 1 1 1 2 1 1 2 4 2 3 1 2 2 2 3 2 1 2 3 1 1 2 1 1 3 1 1 5 2 1 1 2 2 1 2 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #13:

score: 0
Accepted
time: 61ms
memory: 5508kb

input:

29997
5 1 1 1 2 5 1 1 3 1 3 1 5 2 1 1 2 2 4 2 1 4 2 1 4 1 1 2 1 1 1 2 1 1 2 8 1 4 4 1 2 3 2 1 3 1 2 2 2 5 1 4 2 2 3 2 2 2 3 3 2 2 7 4 4 4 1 5 5 2 1 4 1 1 2 2 5 1 1 3 3 1 3 1 1 1 1 2 1 4 3 4 3 2 1 2 2 1 1 1 2 1 3 1 1 1 2 2 2 2 1 2 4 4 3 2 1 3 1 2 1 2 1 1 3 3 3 2 3 2 1 1 2 1 1 1 1 2 2 1 1 2 2 1 1 1 6 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #14:

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

input:

10
2 1 3 2 1 1 2 2 1 3
0 0 2 1 0 1 1 2 1 1
1 1 1 2 0 1 2 0 1 1
0 0 2 0 0 1 1 1 0 1
2 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0...

output:

QUERY 1111111111
QUERY 1010101010
QUERY 0110011001
QUERY 0001111000
QUERY 0000000111
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
QUERY 0000000000
ANSWER
2 10
5 8
6 7
9 3
8 1
...

result:

ok correct answer

Test #15:

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

input:

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

output:

QUERY 11111111
QUERY 10101010
QUERY 01100110
QUERY 00011110
QUERY 00000001
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
QUERY 00000000
ANSWER
1 3
2 5
6 5
7 4
8 4
3 5
4 5

result:

ok correct answer

Test #16:

score: 0
Accepted
time: 63ms
memory: 5696kb

input:

30000
2 1 2 3 1 1 5 3 1 5 3 1 4 1 3 1 1 1 1 2 1 1 1 1 6 2 2 2 1 3 1 6 3 4 1 3 1 1 2 1 1 1 1 3 1 3 1 2 1 1 1 1 1 5 3 5 1 3 1 1 1 1 1 4 2 3 1 1 1 1 3 1 2 1 1 1 1 3 4 1 2 2 1 2 3 1 1 2 1 1 1 2 1 1 1 1 1 1 1 2 2 1 2 2 2 1 3 3 3 4 2 4 2 1 2 1 1 4 1 2 3 4 1 1 1 1 1 2 1 2 1 1 2 6 3 1 2 1 1 3 1 2 2 1 1 2 1 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #17:

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

input:

128
1 2 2 7 3 1 2 2 3 4 1 4 1 1 3 1 1 1 4 3 2 1 3 1 2 1 5 1 2 2 3 1 1 3 3 2 1 1 1 3 1 3 1 1 1 2 3 3 4 3 2 1 7 1 4 1 1 4 4 3 1 3 2 1 2 1 1 1 2 1 1 1 1 1 1 2 3 1 1 1 1 2 2 1 1 1 1 3 2 1 1 1 3 1 1 1 3 2 2 1 3 3 1 3 4 1 1 1 7 1 1 4 1 1 3 2 1 2 2 2 1 6 2 1 1 2 1 1
0 1 0 2 2 1 1 2 1 1 1 4 1 0 3 0 1 0 1 2 ...

output:

QUERY 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
QUERY 10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010
QUERY 011001100110011001100110...

result:

ok correct answer

Test #18:

score: 0
Accepted
time: 51ms
memory: 5708kb

input:

30000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

QUERY 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok correct answer

Test #19:

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

input:

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

output:

QUERY 111
QUERY 101
QUERY 011
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
QUERY 000
ANSWER
1 3
2 3

result:

ok correct answer

Test #20:

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

input:

2
1 1
0 1
1 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

output:

QUERY 11
QUERY 10
QUERY 01
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
QUERY 00
ANSWER
1 2

result:

ok correct answer