QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#472857#8871. Interactive ReconstructionPetroTarnavskyi#TL 0ms0kbC++201.5kb2024-07-11 19:55:172024-07-11 19:55:18

Judging History

This is the latest submission verdict.

  • [2024-07-11 19:55:18]
  • Judged
  • Verdict: TL
  • Time: 0ms
  • Memory: 0kb
  • [2024-07-11 19:55:17]
  • 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 (i)
			cout << ' ';
		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));
		
	}
	cout << *leafs.begin() + 1 << " " << *next(leafs.begin()) + 1 << endl;
	
	
	
	
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Time Limit Exceeded

input:

30000

output:

QUERY 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

result: