Submission #145420

#	Time	Username	Problem	Language	Result	Execution time	Memory
145420		emilem	Zagonetka (COI18_zagonetka)	C++14	100 / 100	215 ms	704 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;
vector< pair<int, int> > rules, rrules;
vector< vector<int> > adj;

void TopSort(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;
		TopSort(to, a);
	}
	a.push_back(v);
}
template<typename T>
ostream& operator<<(ostream& ostr, const vector<T>& a)
{
	for (int i = 1; i < a.size(); ++i)
		ostr << a[i] << ' ';
	return ostr;
}
bool Dfs(int v, vector<int>& a, set<int> visited = set<int>())
{
	used[v] = true;
	visited.insert(v);
	for (int i = 0; i < nei[v].size(); ++i)
	{
		int to = nei[v][i];
		if (visited.count(to))
			return false;
		if (used[to])
			continue;
		if (!Dfs(to, a, visited))
			return false;
	}
	a.push_back(v);
	return true;
}
bool Possible(int k, int i)
{
	vector<int> a;
	fill(used.begin(), used.end(), false);
	for (int v = 1; v <= n; ++v)
		if (p[v] <= p[k] && p[v] >= p[i] && !used[v])
			if (!Dfs(v, a))
				return false;
	reverse(a.begin(), a.end());
	vector<int> p1(p);
	int num = p[i];
	for (int i = 0; i < a.size(); ++i)
		p1[a[i]] = num++;
	/*
	bool f = true;
	for (int i = 0; i < rrules.size(); ++i)
		if (p1[rrules[i].first] >= p1[rrules[i].second])
			f = false;
	return f;
	*/
	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() + 1, p.end(), k) - p.begin();
	vector<int> iVec;
	for (int i = 1; i <= n; ++i)
		if (p[i] < k)
			iVec.push_back(i);
	sort(iVec.begin(), iVec.end(), [](int i, int j) { return p[i] > p[j]; });
	for (int f = 0; f < iVec.size(); ++f)
	{
		int i = iVec[f];
		if (p[i] < k)
		{
			nei[kInd].push_back(i);
			bool f = Possible(kInd, i);
			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];
	/*
	int temp;
	cin >> temp;
	rrules.resize(temp);
	for (int i = 0; i < rrules.size(); ++i)
		cin >> rrules[i].first >> rrules[i].second;
	*/
	Solve(n);
	vector<pair<int, int> > rules;
	adj.resize(n + 1, vector<int>(n + 1));
	for (int v = 1; v <= n; ++v)
		for (int i = 0; i < nei[v].size(); ++i)
		{
			int to = nei[v][i];
			adj[v][to] = true;
		}
	for (int mid = 1; mid <= n; ++mid)
		for (int u = 1; u <= n; ++u)
			for (int v = 1; v <= n; ++v)
				if (adj[u][mid] && adj[mid][v])
					adj[u][v] = true;
	fill(nei.begin(), nei.end(), vector<int>());
	for (int u = 1; u <= n; ++u)
		for (int v = 1; v <= n; ++v)
			if (adj[u][v])
				nei[u].push_back(v);
	for (int v = 1; v <= n; ++v)
		for (int i = 0; i < nei[v].size(); ++i)
		{
			int to = nei[v][i];
			// cout << v << ' ' << to << endl;
		}
	fill(used.begin(), used.end(), false);
	vector<int> a/*(n + 1)*/;
	for (int i = 1; i <= n; ++i)
		if (!used[i])
			TopSort(i, a);
	vector<int> largest(n + 1);
	reverse(a.begin(), a.end());
	int num = 1;
	for (int i = 0; i < a.size(); ++i)
		largest[a[i]] = num++;

	fill(nei.begin(), nei.end(), vector<int>());
	for (int u = 1; u <= n; ++u)
		for (int v = 1; v <= n; ++v)
			if (adj[u][v])
				nei[v].push_back(u);
	fill(used.begin(), used.end(), false);
	a.clear();
	for (int i = 1; i <= n; ++i)
		if (!used[i])
			TopSort(i, a);
	vector<int> smallest(n + 1);
	reverse(a.begin(), a.end());
	num = 1;
	for (int i = 0; i < a.size(); ++i)
		smallest[a[i]] = (n - num++ + 1);
	cout << "end\n" << smallest << endl << largest << endl;
	fill(used.begin(), used.end(), false);
	/*
	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;
	*/
}

Compilation message (stderr)

zagonetka.cpp: In function 'void TopSort(int, std::vector<int>&)':
zagonetka.cpp:17: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 Dfs(int, std::vector<int>&, std::set<int>)':
zagonetka.cpp:37: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, int)':
zagonetka.cpp:61:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i)
                  ~~^~~~~~~~~~
zagonetka.cpp: In function 'void Solve(int)':
zagonetka.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int f = 0; f < iVec.size(); ++f)
                  ~~^~~~~~~~~~~~~
zagonetka.cpp: In function 'int main()':
zagonetka.cpp:119:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < nei[v].size(); ++i)
                   ~~^~~~~~~~~~~~~~~
zagonetka.cpp:135:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < nei[v].size(); ++i)
                   ~~^~~~~~~~~~~~~~~
zagonetka.cpp:137:8: warning: unused variable 'to' [-Wunused-variable]
    int to = nei[v][i];
        ^~
zagonetka.cpp:148:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); ++i)
                  ~~^~~~~~~~~~
zagonetka.cpp:164:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.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:70:22:   required from here
zagonetka.cpp:29:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < a.size(); ++i)

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