QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#472863 | #8871. Interactive Reconstruction | PetroTarnavskyi | AC ✓ | 113ms | 6896kb | C++23 | 1.4kb | 2024-07-11 19:58:57 | 2024-07-11 19:58:57 |
Judging History
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