oj.uz

Submission #145420

# Submission time Handle Problem Language Result Execution time Memory
145420 2019-08-19T20:02:48 Z emilem Zagonetka (COI18_zagonetka) C++14
100 / 100
 215 ms 704 KB 
#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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 404 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 248 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 248 KB Output is correct
2 Correct 35 ms 376 KB Output is correct
3 Correct 43 ms 340 KB Output is correct
4 Correct 44 ms 376 KB Output is correct
5 Correct 14 ms 376 KB Output is correct
6 Correct 45 ms 248 KB Output is correct
7 Correct 8 ms 376 KB Output is correct
8 Correct 11 ms 248 KB Output is correct
9 Correct 44 ms 424 KB Output is correct
10 Correct 21 ms 420 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 10 ms 248 KB Output is correct
5 Correct 4 ms 248 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 6 ms 248 KB Output is correct
8 Correct 9 ms 332 KB Output is correct
9 Correct 7 ms 336 KB Output is correct
10 Correct 3 ms 412 KB Output is correct
11 Correct 9 ms 376 KB Output is correct
12 Correct 5 ms 416 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 336 KB Output is correct
2 Correct 106 ms 380 KB Output is correct
3 Correct 77 ms 344 KB Output is correct
4 Correct 146 ms 664 KB Output is correct
5 Correct 211 ms 704 KB Output is correct
6 Correct 215 ms 636 KB Output is correct
7 Correct 32 ms 504 KB Output is correct
8 Correct 42 ms 380 KB Output is correct
9 Correct 38 ms 384 KB Output is correct
10 Correct 108 ms 380 KB Output is correct
11 Correct 82 ms 360 KB Output is correct
12 Correct 87 ms 376 KB Output is correct
13 Correct 78 ms 348 KB Output is correct
14 Correct 86 ms 424 KB Output is correct
15 Correct 89 ms 480 KB Output is correct
16 Correct 101 ms 344 KB Output is correct