QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#472842 | #8871. Interactive Reconstruction | PetroTarnavskyi# | TL | 0ms | 0kb | C++20 | 1.4kb | 2024-07-11 19:49:38 | 2024-07-11 19:49:38 |
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 = 3;
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\n";
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 << "\n";
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));
}
cout << *leafs.begin() + 1 << " " << *next(leafs.begin()) + 1 << endl;
return 0;
}
詳細信息
Test #1:
score: 0
Time Limit Exceeded
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...