oj.uz

Submission #643580

# Submission time Handle Problem Language Result Execution time Memory
643580 2022-09-22T14:29:48 Z gun_gan Zagonetka (COI18_zagonetka) C++17
0 / 100
 32 ms 336 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 105;
int n, a[N], m, deg[N], mn[N], mx[N], Deg[N], order[N];
vector<int> g[N], ng[N];

vector<int> toposort() {
	vector<int> d(n + 1);
	for(int i = 1; i <= n; i++) {
		for(auto u : g[i]) {
			// cout << i << " -> " << u << endl;
			d[u]++;
		}
	}

	queue<int> q;
	for(int i = 1; i <= n; i++) {
		if(!d[i]) q.push(i);
		// cout << d[i] << " ";
	}
	// cout << endl;

	vector<int> ret(n + 1);
	int cnt = 0;
	while(!q.empty()) {
		int v = q.front(); q.pop();
		ret[v] = ++cnt;
		for(auto u : g[v]) {
			d[u]--;
			if(d[u] == 0) {
				q.push(u);
			}
		}
	}
	assert(cnt == n);
	return ret;

}

bool ask(int l, int r)
{
	auto v = toposort();
	cout << "query ";
	for(int i = 1; i <= n; i++) cout << v[i] << " ";
	cout << endl;

	int x;
	cin >> x;
	return x;
}

int main() 
{
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin >> n;	
	for(int i = 1; i <= n; i++) cin >> a[i];

	if(0) {
		vector<int> p, mx, mn;
		for(int i = 1; i <= n; i++) p.push_back(i);
		do {
			cout << "query ";
			for(int i = 0; i < n; i++) {
				cout << p[i] << " ";
			}
			cout << endl;

			int x; cin >> x;
			if(x) {
				if(mx.empty()) {
					mx = p;
				} else {
					if(p > mx) mx = p;
				}
				if(mn.empty()) mn = p;
				else if(p < mn) mn = p;
			}
		} while(next_permutation(p.begin(), p.end()));

		cout << "end\n";
		for(auto i : mn) cout << i << " ";
		cout << '\n';
		for(auto i : mx) cout << i << " ";
		cout << endl;
		return 0;
	}

	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(a[j] > a[order[i - 1]] && (a[order[i]] == 0 || a[order[i]] > a[j])) {
				order[i] = j;
			}
		}
	}

	for(int i = 1; i <= n; i++) {
		for(int j = i + 1; j <= n; j++) {
			g[order[i]].push_back(order[j]);
		}
	}

	bool f = 0;
	for(int i = 1; i <= n && !f; i++) {
		for(int j = i + 1; j <= n; j++) {
			auto it = find(g[order[i]].begin(), g[order[i]].end(), order[j]);
			g[order[i]].erase(it);
			g[order[j]].push_back(order[i]);
			if(!ask(i, j)) {
				auto it = find(g[order[j]].begin(), g[order[j]].end(), order[i]);
				g[order[j]].erase(it);
				g[order[i]].push_back(order[j]);
				ng[order[i]].push_back(order[j]);
				deg[order[j]]++;
				Deg[order[j]]++;
				f = 1;
				break;
			} else {
				auto it = find(g[order[j]].begin(), g[order[j]].end(), order[i]);
				g[order[j]].erase(it);
			}
 		}	
	}

	priority_queue<int> q;
	for(int i = 1; i <= n; i++) if(!deg[i]) q.push(i);
	int cnt = 0;
	while(!q.empty()) {
		int v = q.top(); q.pop();
		mx[v] = ++cnt;
		for(auto u : ng[v]) {
			deg[u]--;
			if(deg[u] == 0) {
				q.push(u);
			}
		}
	}

	for(int i = 1; i <= n; i++) if(!Deg[i]) q.push(-i);

	cnt = 0;
	while(!q.empty()) {
		int v = q.top(); q.pop();
		v = -v;
		mn[v] = ++cnt;
		for(auto u : ng[v]) {
			Deg[u]--;
			if(Deg[u] == 0) {
				q.push(-u);
			}
		}
	}

	// for(int i = 1; i <= n; i++) {
	// 	for(auto v : ng[i]) {
	// 		cout << i << " -> " << v << '\n';
	// 	}
	// }

	cout << "end\n";
	for(int i = 1; i <= n; i++) cout << mn[i] << " ";
	cout << '\n';
	for(int i = 1; i <= n; i++) cout << mx[i] << " ";
	cout << endl;

}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 208 KB Output is correct
2 Incorrect 13 ms 208 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -