Submission #145112

#	Time	Username	Problem	Language	Result	Execution time	Memory
145112		emilem	Zagonetka (COI18_zagonetka)	C++14	0 / 100	3035 ms	380 KiB

zagonetka

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
using namespace std;

int n;
vector<bool> used;
vector<int> p;
vector< vector<int> > nei;

template<typename T>
ostream& operator<<(ostream& ostr, const vector<T>& a)
{
	for (int i = 0; i < a.size(); ++i)
		ostr << a[i] << ' ';
	return ostr;
}
void Dfs(int v, vector<int>& a)
{
	used[v] = true;
	for (int i = 0; i < nei[v].size(); ++i)
	{
		int to = nei[v][i];
		if (used[to])
			continue;
		Dfs(to, a);
	}
	a.push_back(v);
}
bool Possible(int k)
{
	vector<int> a;
	fill(used.begin(), used.end(), false);
	for (int v = 1; v <= n; ++v)
		if (p[v] <= k && !used[v])
			Dfs(v, a);
	reverse(a.begin(), a.end());
	vector<int> p1(p);
	int num = 1;
	for (int i = 0; i < a.size(); ++i)
		p[a[i]] = num++;
	cout << "query " << p1 << endl;
	int res;
	cin >> res;
	return res;
}
void Solve(int k)
{
	if (k == 1)
		return;
	Solve(k - 1);
	int kInd = find(p.begin(), p.end(), k) - p.begin();
	for (int i = 1; i <= n; ++i)
		if (p[i] < k)
		{
			nei[kInd].push_back(i);
			bool f = Possible(k);
			nei[kInd].pop_back();
			if (!f)
				nei[i].push_back(kInd);
		}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n;
	nei.resize(n + 1); p.resize(n + 1); used.resize(n + 1);
	for (int i = 1; i <= n; ++i)
		cin >> p[i];
	Solve(n);
	vector<int> l, r;
	vector<int> ans(n);
	for (int i = 0; i < n; ++i)
		ans[i] = i + 1;
	do {
		bool f = true;
		for (int v = 1; v <= n; ++v)
			for (int i = 0; i < nei[v].size(); ++i)
			{
				int to = nei[v][i];
				if (ans[v - 1] >= ans[to - 1])
					f = false;
				// cout << v << ' ' << to << endl;
			}
		if (f)
		{
			r = ans;
			if (l.empty())
				l = ans;
		}
	} while(next_permutation(ans.begin(), ans.end()));
	cout << "end\n" << l << '\n' << r << endl;

	char I;
	cin >> I;
}

Compilation message (stderr)

zagonetka.cpp: In function 'void Dfs(int, std::vector<int>&)':
zagonetka.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < nei[v].size(); ++i)
                  ~~^~~~~~~~~~~~~~~
zagonetka.cpp: In function 'bool Possible(int)':
zagonetka.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i)
                  ~~^~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < nei[v].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
zagonetka.cpp: In instantiation of 'std::ostream& operator<<(std::ostream&, const std::vector<T>&) [with T = int; std::ostream = std::basic_ostream<char>]':
zagonetka.cpp:43:22:   required from here
zagonetka.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i)

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