oj.uz

Submission #422107

# Submission time Handle Problem Language Result Execution time Memory
422107 2021-06-09T17:48:18 Z Berted Zagonetka (COI18_zagonetka) C++14
100 / 100
 168 ms 416 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 1 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 200 KB Output is correct
5 Correct 1 ms 200 KB Output is correct
6 Correct 1 ms 200 KB Output is correct
7 Correct 1 ms 200 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 200 KB Output is correct
2 Correct 39 ms 200 KB Output is correct
3 Correct 47 ms 200 KB Output is correct
4 Correct 42 ms 200 KB Output is correct
5 Correct 12 ms 200 KB Output is correct
6 Correct 46 ms 200 KB Output is correct
7 Correct 6 ms 200 KB Output is correct
8 Correct 10 ms 200 KB Output is correct
9 Correct 32 ms 200 KB Output is correct
10 Correct 16 ms 200 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 200 KB Output is correct
2 Correct 3 ms 300 KB Output is correct
3 Correct 6 ms 200 KB Output is correct
4 Correct 8 ms 200 KB Output is correct
5 Correct 5 ms 300 KB Output is correct
6 Correct 7 ms 304 KB Output is correct
7 Correct 5 ms 200 KB Output is correct
8 Correct 6 ms 200 KB Output is correct
9 Correct 6 ms 200 KB Output is correct
10 Correct 3 ms 200 KB Output is correct
11 Correct 6 ms 200 KB Output is correct
12 Correct 7 ms 200 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 200 KB Output is correct
2 Correct 93 ms 200 KB Output is correct
3 Correct 64 ms 200 KB Output is correct
4 Correct 134 ms 280 KB Output is correct
5 Correct 143 ms 416 KB Output is correct
6 Correct 168 ms 320 KB Output is correct
7 Correct 120 ms 304 KB Output is correct
8 Correct 121 ms 304 KB Output is correct
9 Correct 131 ms 308 KB Output is correct
10 Correct 108 ms 280 KB Output is correct
11 Correct 84 ms 200 KB Output is correct
12 Correct 94 ms 200 KB Output is correct
13 Correct 98 ms 280 KB Output is correct
14 Correct 108 ms 284 KB Output is correct
15 Correct 111 ms 292 KB Output is correct
16 Correct 100 ms 200 KB Output is correct