Submission #70793

#	Time	Username	Problem	Language	Result	Execution time	Memory
70793		Bruteforceman	Zagonetka (COI18_zagonetka)	C++11	100 / 100	165 ms	976 KiB

zagonetka

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

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];
bool vis[111];

void dfs(int x) {
	vis[x] = true;
	for(auto i : g[x]) {
		if(!vis[i]) {
			dfs(i);
		}
	}
} 

vector <int> A;
bool del[111];
bool visit[111];
set <int> reach[111];

void travel(int x) {
	if(visit[x]) return ;
	visit[x] = true;
	reach[x].insert(x);
	for(auto i : g[x]) {
		travel(i);
		for(auto j : reach[i]) {
			reach[x].insert(j);
		}
	}
}
void solve(int x) {
	del[x] = true;
	for(auto i : reach[x]) {
		if(del[i]) continue;
		solve(i);
	}
	A.push_back(x);
}

vector <int> order(vector <pii> e) {
	for(int i = 0; i < n; i++) {
		g[i].clear();
		reach[i].clear();
	}
	for(int i = 0; i < e.size(); i++) {
		g[e[i].second].push_back(e[i].first);
	}
	memset(visit, false, sizeof visit);
	memset(del, false, sizeof del);
	for(int i = 0; i < n; i++) {
		travel(i);
	}
	A.clear();
	for(int i = 0; i < n; i++) {
		if(!del[i]) solve(i);
	}
	return A;
}

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;
	}
	vector <pii> edge;
	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) {
					dfs(p[j]);
					edge.emplace_back(p[i], p[j]);
					// cerr << p[i]+1 << ' ' << p[j]+1 << endl;
				}
			}
		}
	}
	// cerr << cnt << endl;
	cout << "end" << endl;
	vector <int> ans (n);

	vector <int> small = order(edge);
	for(int i = 0; i < edge.size(); i++) {
		swap(edge[i].first, edge[i].second);
	}
	vector <int> big = order(edge);
	reverse(big.begin(), big.end());
	for(int i = 0; i < n; i++) {
		ans[small[i]] = i;
	}
	for(auto i : ans) {
		cout << i+1 << ' ';
	}
	cout << endl;
	for(int i = 0; i < n; i++) {
		ans[big[i]] = i;
	}
	for(auto i : ans) {
		cout << i+1 << ' ';
	}
	cout << endl;
	return 0;
}

Compilation message (stderr)

zagonetka.cpp: In function 'std::vector<int> order(std::vector<std::pair<int, int> >)':
zagonetka.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < e.size(); i++) {
                 ~~^~~~~~~~~~
zagonetka.cpp: In function 'int main(int, const char**)':
zagonetka.cpp:121:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < edge.size(); i++) {
                 ~~^~~~~~~~~~~~~

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