QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#472863#8871. Interactive ReconstructionPetroTarnavskyiAC ✓113ms6896kbC++231.4kb2024-07-11 19:58:572024-07-11 19:58:57

Judging History

This is the latest submission verdict.

  • [2024-07-11 19:58:57]
  • Judged
  • Verdict: AC
  • Time: 113ms
  • Memory: 6896kb
  • [2024-07-11 19:58:57]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;

int n;
VI query(int bit)
{
	cout << "QUERY ";
	FOR(i, 0, n)
	{
		if(bit == -1)
		{
			cout << "1";
			continue;
		}
		cout << ((i >> bit) & 1);
	}
	cout << endl;
	VI res(n);
	FOR(i, 0, n)
		cin >> res[i];
	return res;
}

const int LOG = 15;

int main()
{
	//ios::sync_with_stdio(0);
	//cin.tie(0);
	
	cin >> n;
	
	
	VI sz = query(-1);
	vector<VI> vals(LOG);
	FOR(bit, 0, LOG)
		vals[bit] = query(bit);
	
	int cnt = n;
	set<int> leafs;
	FOR(i, 0, n)
		if(sz[i] == 1)
			leafs.insert(i);
	
	VI used(n);
	
	cout << "ANSWER" << endl;
	while(cnt > 2)
	{
		VI nleafs;
		for(int v : leafs)
		{
			used[v] = 1;
			int par = 0;
			FOR(bit, 0, LOG)
				par |= vals[bit][v] << bit;
			cout << v + 1 << " " << par + 1 << endl;
			cnt--;
			
			FOR(bit, 0, LOG)
				vals[bit][par] -= (v >> bit) & 1;
			sz[par]--;
			if(sz[par] == 1)
				nleafs.PB(par);
		}
		leafs.clear();
		leafs.insert(ALL(nleafs));
		
	}
if(cnt == 2)
	cout << *leafs.begin() + 1 << " " << *next(leafs.begin()) + 1 << endl;
	
	
	
	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 111ms
memory: 6232kb

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: 46ms
memory: 4952kb

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: 1ms
memory: 3796kb

input:

8
1 3 2 1 3 1 1 2
1 0 1 0 2 1 1 1
0 2 0 0 3 1 0 0
0 1 1 1 1 1 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
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 01010101
QUERY 00110011
QUERY 00001111
QUERY 00000000
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
2 3
8 5
3 5

result:

ok correct answer

Test #4:

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

input:

4
1 1 1 3
1 1 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 0
0 0 0 0
0 0 0 0
0 0 0 0

output:

QUERY 1111
QUERY 0101
QUERY 0011
QUERY 0000
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: 104ms
memory: 5600kb

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: 104ms
memory: 5716kb

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: 100ms
memory: 5584kb

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: 98ms
memory: 5800kb

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: 1ms
memory: 3600kb

input:

8
2 2 2 1 2 2 1 2
2 1 1 0 1 0 1 1
1 2 0 0 2 1 0 0
1 2 2 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 0 0 0 0 0

output:

QUERY 11111111
QUERY 01010101
QUERY 00110011
QUERY 00001111
QUERY 00000000
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: 96ms
memory: 6348kb

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: 85ms
memory: 6336kb

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: 106ms
memory: 6356kb

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: 92ms
memory: 6356kb

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

input:

10
2 1 3 2 1 1 2 2 1 3
2 1 1 1 1 0 1 0 0 2
1 0 2 1 1 1 1 0 1 1
1 0 1 0 1 1 1 1 0 0
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 0...

output:

QUERY 1111111111
QUERY 0101010101
QUERY 0011001100
QUERY 0000111100
QUERY 0000000011
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
7 3
...

result:

ok correct answer

Test #15:

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

input:

8
1 1 2 3 4 1 1 1
0 0 0 1 3 0 1 1
1 0 0 2 2 0 1 1
0 1 1 3 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

output:

QUERY 11111111
QUERY 01010101
QUERY 00110011
QUERY 00001111
QUERY 00000000
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: 113ms
memory: 6568kb

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

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
1 1 2 5 1 0 1 0 2 3 0 0 0 1 0 1 0 1 3 1 ...

output:

QUERY 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
QUERY 01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
QUERY 001100110011001100110011...

result:

ok correct answer

Test #18:

score: 0
Accepted
time: 95ms
memory: 6896kb

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: 1ms
memory: 3600kb

input:

3
1 1 2
0 0 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

output:

QUERY 111
QUERY 010
QUERY 001
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: 0ms
memory: 3800kb

input:

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

output:

QUERY 11
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
QUERY 00
ANSWER
1 2

result:

ok correct answer