#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 << 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;
*/
char I;
cin >> I;
}
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:65:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < rrules.size(); ++i)
~~^~~~~~~~~~~~~~~
zagonetka.cpp: In function 'void Solve(int)':
zagonetka.cpp:87: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:112:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < rrules.size(); ++i)
~~^~~~~~~~~~~~~~~
zagonetka.cpp:118:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < nei[v].size(); ++i)
~~^~~~~~~~~~~~~~~
zagonetka.cpp:134:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < nei[v].size(); ++i)
~~^~~~~~~~~~~~~~~
zagonetka.cpp:136:8: warning: unused variable 'to' [-Wunused-variable]
int to = nei[v][i];
^~
zagonetka.cpp:147:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.size(); ++i)
~~^~~~~~~~~~
zagonetka.cpp:163: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:165:10: 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)
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2 ms |
376 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2 ms |
376 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2 ms |
248 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2 ms |
376 KB |
Time limit exceeded (wall clock) |
| 2 |
Halted |
0 ms |
0 KB |
- |
