Submission #70446

#	Time	Username	Problem	Language	Result	Execution time	Memory
70446		Bruteforceman	Zagonetka (COI18_zagonetka)	C++11	0 / 100	6 ms	344 KiB

zagonetka

#include "bits/stdc++.h"
using namespace std;
int n;
vector <int> p;

bool query(vector <int> v) {
	vector <int> p (v.size());
	for(size_t i = 0; i < v.size(); i++) {
		p[v[i]] = i;
	}
	cout << "query";
	for(auto i : p) {
		cout << " " << (i+1);
	}
	cout << endl;
	int ans;
	cin >> ans;
	return ans;
}

vector <int> g[111];
vector <int> rev[111];
bool vis[111];
void dfs(int x) {
	vis[x] = true;
	for(auto i : g[x]) {
		if(!vis[i]) {
			dfs(i);
		}
	}
} 

int mx[111];
int mn[111];
int in[111];

void dp(int x) {
	mn[x] = x;
	for(auto i : g[x]) {
		if(!vis[i]) dp(i);
		mn[x] = min(mn[x], mn[i]);
	}
}
void fn(int x) {
	mn[x] = x;
	for(auto i : rev[x]) {
		if(!vis[i]) fn(i);
		mn[x] = min(mn[x], mn[i]);
	}
}

int main(int argc, char const *argv[])
{
	cin >> n;
	p.resize(n);
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		p[x-1] = i;
	}
	int cnt = 0;
	for(int i = n-1; i >= 0; i--) {
		memset(vis, false, sizeof vis);
		for(int j = i+1; j < n; j++) {
			if(vis[p[j]] == false) {	
				// cout << p[i]+1 << " with " << p[j]+1 << endl;
				vector <int> tmp;
				for(int k = 0; k < i; k++) {
					tmp.emplace_back(p[k]);
				}
				for(int k = i+1; k <= j; k++) {
					if(vis[p[k]] == false) {
						tmp.emplace_back(p[k]);
					}
				}
				tmp.emplace_back(p[i]);
				for(int k = i+1; k < n; k++) {
					if(vis[p[k]] == false && k <= j) continue;
					tmp.emplace_back(p[k]);
				}
				if(query(tmp) == 0) {
					g[p[i]].emplace_back(p[j]);
					rev[p[j]].emplace_back(p[i]);
					dfs(p[j]);
					cerr << p[i]+1 << ' ' << p[j]+1 << endl;
					++cnt;
				}
			}
		}
	}
	cerr << cnt << endl;
	cout << "end" << endl;

	typedef pair <int, int> pii;
	priority_queue <pii> P;
	priority_queue <pii, vector <pii>, greater <pii>> Q;
	vector <int> small, big;

	memset(in, 0, sizeof in);
	for(int i = 0; i < n; i++) {
		for(int j : g[i]) {
			++in[j];
		}
	}
	memset(vis, false, sizeof vis);
	for(int i = 0; i < n; i++) {
		if(!vis[i]) {
			dp(i);
		}
	}
	for(int i = 0; i < n; i++) {
		if(in[i] == 0) {
			Q.push(pii(mn[i], i));
		}
	}
	while(!Q.empty()) {
		int x = Q.top().second;
		Q.pop();
		small.push_back(x);
		for(int i : g[x]) {
			--in[i];
			if(in[i] == 0) {
				Q.push(pii(mn[i], i));
			}
		}
	}

	memset(in, 0, sizeof in);
	for(int i = 0; i < n; i++) {
		for(int j : rev[i]) {
			++in[j];
		}
	}
	memset(vis, false, sizeof vis);
	for(int i = 0; i < n; i++) {
		if(!vis[i]) {
			fn(i);
		}
	}
	for(int i = 0; i < n; i++) {
		if(in[i] == 0) {
			Q.push(pii(mn[i], i));
		}
	}
	while(!Q.empty()) {
		int x = Q.top().second;
		Q.pop();
		big.push_back(x);
		for(int i : rev[x]) {
			--in[i];
			if(in[i] == 0) {
				Q.push(pii(mn[i], i));
			}
		}
	}
	reverse(big.begin(), big.end());

	vector <int> ans (n);
	for(int i = 0; i < n; i++) {
		ans[small[i]] = i;
	}
	for(int i : ans) {
		cout << i+1 << ' ';
	}
	cout << endl;
	for(int i = 0; i < n; i++) {
		ans[big[i]] = i;
	}
	for(int i : ans) {
		cout << i+1 << ' ';
	}
	cout << endl;
	return 0;
}

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