Submission #422107

#	Time	Username	Problem	Language	Result	Execution time	Memory
422107		Berted	Zagonetka (COI18_zagonetka)	C++14	100 / 100	168 ms	416 KiB

zagonetka

#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#define vi vector<int>

using namespace std;

int N, A[101], P[101], B[101];
vi adj[101], rev[101];

vi topo;

int cnt = 0;
bool vis[101];

bool query()
{
	cout << "query";
	for (int i = 0; i < N; i++) cout << " " << B[i];
	cout << endl;
	bool x; cin >> x;
	return x;
}

void DFS(int u)
{
	if (vis[u]) return;
	vis[u] = 1;

	for (const auto &v : adj[u]) {DFS(v);}
	//cerr << "DFS: " << u << "\n";
	topo.push_back(u);
}

void DFS2(int u)
{
	if (vis[u]) return;
	vis[u] = 1;

	sort(rev[u].begin(), rev[u].end());

	for (const auto &v : rev[u]) {DFS2(v);}
	B[u] = ++cnt;
}

void DFS3(int u)
{
	if (vis[u]) return;
	vis[u] = 1;

	sort(adj[u].begin(), adj[u].end());

	for (const auto &v : adj[u]) {DFS3(v);}
	B[u] = cnt--;
}

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++) {cin >> A[i]; P[A[i] - 1] = i;}
	for (int i = 1; i < N; i++)
	{
		for (int j = i - 1; j >= 0; j--)
		{
			int ss = 0;
			//cerr << "CHECKING: " << i << " " << j << ", " << P[i] << " <- " << P[j] << "\n";
			for (int k = 0; k < N; k++) vis[P[k]] = (k >= i);

			DFS(P[j]); ss = topo.size();
			for (int k = 0; k < i; k++)
			{
				if (!vis[P[k]]) 
				{
					//cerr << "NEW INSTANCE\n";
					DFS(P[k]); 
				}
			}

			reverse(topo.begin(), topo.end());
			topo.insert(topo.end() - ss, P[i]);

			//cerr << "TOPO: ";
			//for (int k = 0; k < topo.size(); k++) cerr << topo[k] << " \n"[k + 1 == topo.size()];
			for (int k = i + 1; k < N; k++) topo.push_back(P[k]);
			for (int k = 0; k < N; k++) B[topo[k]] = k + 1;

			if (query() == 0) 
			{
				//cerr << "ADD EDGE: " << P[j] << " -> " << P[i] << "\n";
				adj[P[j]].push_back(P[i]);
			}

			topo.clear();
		}
	}

	for (int u = 0; u < N; u++)
	{
		vis[u] = 0;
		for (const auto &v : adj[u]) rev[v].push_back(u);
	}

	for (int u = 0; u < N; u++) DFS2(u);

	cout << "end" << endl;
	for (int u = 0; u < N; u++) 
	{
		cout << B[u] << " \n"[u == N + 1];
	}

	for (int u = 0; u < N; u++) vis[u] = 0;
	for (int u = 0; u < N; u++) DFS3(u);
	for (int u = 0; u < N; u++) 
	{
		cout << B[u] << " \n"[u == N + 1];
	}
	cout << flush;
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 51 / 51