Submission #276950

#	Time	Username	Problem	Language	Result	Execution time	Memory
276950		Plurm	Zagonetka (COI18_zagonetka)	C++11	18 / 100	100 ms	384 KiB

zagonetka

#include <bits/stdc++.h>
using namespace std;

int n;
int query(vector<int> v){
	cout << "query";
	for (int i = 0; i < n; i++) cout << " " << v[i];
	cout << endl << flush;
	int result;
	cin >> result;
	return result;
}
void answer(vector<int> lo, vector<int> hi){
	cout << "end" << endl << flush;
	for(int i = 0; i < n; i++) cout << lo[i] << " ";
	cout << endl << flush;
	for(int i = 0; i < n; i++) cout << hi[i] << " ";
	cout << endl << flush;
}
int revmap[128];

// u <-- v iff u < v req.
vector<int> g[128]; // No SCC (guaranteed)
vector<int> rg[128]; // Reversed

void dfstopo(int u, int lim, vector<int>& ord, vector<bool>& found){
	if(found[u]) return;
	found[u] = true;
	for(int v : g[u]){
		if(v < lim) continue;
		dfstopo(v, lim, ord, found);
	}
	ord.push_back(u);
}

void dfshigher(int u, vector<bool>& found){
	if(found[u]) return;
	found[u] = true;
	for(int v : rg[u]){
		dfshigher(v, found);
	}
}

void dfsless(int u, int lim, vector<bool>& found){
	if(found[u]) return;
	found[u] = true;
	for(int v : g[u]){
		if(v < lim) continue;
		dfsless(v, lim, found);
	}
}

/**
 * Determines whether x < y is a required order or not?
 */
bool customLess(int x, int y){
	vector<bool> found;
	found.reserve(n+1);
	for(int i = 0; i <= n; i++) found.push_back(false);
	dfsless(y, x, found);
	return found[x];
}
/**
 * Get topological ordering (any) with start as source, going down until vertex value less than lim.
 */
vector<int> getTopo(int start, int lim){
	vector<int> ord;
	vector<bool> found;
	found.reserve(n+1);
	for(int i = 0; i <= n; i++) found.push_back(false);
	dfstopo(start, lim, ord, found);
	return ord;
}

vector<int> getLower(int start){
	vector<int> ord;
	vector<bool> found;
	found.reserve(n+1);
	for(int i = 0; i <= n; i++) found.push_back(false);
	dfsless(start, 0, found);
	for(int i = 0; i <= n; i++) if(found[i]) ord.push_back(i);
	return ord;
}

vector<int> getHigher(int start){
	vector<int> ord;
	vector<bool> found;
	found.reserve(n+1);
	for(int i = 0; i <= n; i++) found.push_back(false);
	dfshigher(start, found);
	for(int i = n; i >= 0; i--) if(found[i]) ord.push_back(i);
	return ord;
}
vector<int> p;
vector<int> minSolve(){
	vector<int> pluggedval;
	for(int i = 0; i < n; i++) pluggedval.push_back(-1);
	int i = 1;
	for(int ptr = 0; ptr < n; ptr++){
		// Plugging i into p[ptr]
		if(pluggedval[ptr] != -1){
			continue;
		}
		vector<int> concern = getLower(p[ptr]);
		for(int u : concern){
			if(pluggedval[revmap[u]] == -1){
				pluggedval[revmap[u]] = i++;
			}
		}
	}
	return pluggedval;
}
vector<int> maxSolve(){
	vector<int> pluggedval;
	for(int i = 0; i < n; i++) pluggedval.push_back(-1);
	int i = n;
	for(int ptr = 0; ptr < n; ptr++){
		// Plugging i into p[ptr]
		if(pluggedval[ptr] != -1){
			continue;
		}
		vector<int> concern = getHigher(p[ptr]);
		for(int u : concern){
			if(pluggedval[revmap[u]] == -1){
				pluggedval[revmap[u]] = i--;
			}
		}
	}
	return pluggedval;
}
int main() {
	cin >> n;
	for(int i = 0; i < n; i++){
		int x;
		cin >> x;
		p.push_back(x);
		revmap[x] = i;
	}
	for(int itv = 1; itv <= n; itv++){
		for(int i = 1; i+itv <= n; i++){
			int j = i+itv;
			if(customLess(i, j)){
				;// do nothing because i < j already 
			}else{
				vector<int> topo = getTopo(j, i);
				int cnt = i;
				for(int u : topo){
					p[revmap[u]] = cnt++;
				}
				sort(topo.begin(), topo.end());
				for(int k = i; k <= j; k++){
					if(!binary_search(topo.begin(), topo.end(), k)){
						p[revmap[k]] = cnt++;
					}
				}
				int req = query(p) == 0;
				for(int k = i; k <= j; k++){
					p[revmap[k]] = k;
				}
				if(req) g[j].push_back(i);
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j : g[i]) rg[j].push_back(i);
	}
	vector<int> lo = minSolve();
	vector<int> hi = maxSolve();
	answer(lo, hi);
	return 0;
}

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