oj.uz

Submission #145107

# Submission time Handle Problem Language Result Execution time Memory
145107 2019-08-18T19:11:35 Z emilem Zagonetka (COI18_zagonetka) C++14
0 / 100
 3000 ms 376 KB 
#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 = 1; 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 << 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 + 1);
	for (int i = 1; i <= n; ++i)
		ans[i] = i;
	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] >= ans[to])
					f = false;
				// cout << v << ' ' << to << endl;

			}
		if (f)
		{
			r = ans;
			if (l == vector<int>())
				l = ans;
		}
	} while(next_permutation(ans.begin() + 1, ans.end()));
	cout << l << '\n' << r << endl;

	char I;
	cin >> I;
}

Compilation message

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:10:   required from here
zagonetka.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < a.size(); ++i)

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB not a valid comman
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3041 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3053 ms 376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3059 ms 248 KB Time limit exceeded
2 Halted 0 ms 0 KB -