#include <bits/stdc++.h>
#define ll long long
#define TASKNAME ""
using namespace std;
const int INF = 1e9 + 7;
const int MAXN = 1e6 + 7;
const double EPS = 1e-8;
vector <vector <int> > gr;
vector <vector <int> > rev_gr;
int n;
vector <int> p;
vector <int> pos;
void query(vector <int> &a) {
cout << "query ";
for (int x : a) {
cout << x + 1 << " ";
}
cout << endl;
}
vector <bool> used;
void dfs(int v) {
if (used[v]) return;
used[v] = 1;
for (int u : rev_gr[v]) {
dfs(u);
}
}
vector <int> lvls;
vector <bool> used1;
void lvl_dfs(int v, int h) {
if (used1[v]) return;
used1[v] = 1;
if (h == lvls.size()) {
lvls.push_back(-INF);
}
lvls[h] = max(lvls[h], v);
for (int u : gr[v]) {
lvl_dfs(u, h + 1);
}
}
void rev_lvl_dfs(int v, int h) {
if (used1[v]) return;
used1[v] = 1;
if (h == lvls.size()) {
lvls.push_back(INF);
}
lvls[h] = min(lvls[h], v);
for (int u : rev_gr[v]) {
rev_lvl_dfs(u, h + 1);
}
}
int main() {
#ifdef MY
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#else
//freopen(TASKNAME".in", "r", stdin);
//freopen(TASKNAME".out", "w", stdout);
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
#endif // MY
cin >> n;
p.resize(n);
pos.resize(n, 0);
for (int i = 0; i < n; i++) {
cin >> p[i];
p[i]--;
pos[p[i]] = i;
}
gr.resize(n);
rev_gr.resize(n);
for (int i = n - 1; i >= 0; i--) {
used.assign(n, 0);
for (int j = i + 1; j < n; j++) {
if (used[j]) {
gr[j].push_back(i);
rev_gr[i].push_back(j);
continue;
}
auto q = p;
lvls.clear();
used1.assign(n, 0);
lvl_dfs(j, 0);
lvls.push_back(i);
for (int x = 0; x < (int) lvls.size() - 1; x++) {
swap(q[pos[lvls[x]]], q[pos[lvls[x + 1]]]);
}
lvls.clear();
used1.assign(n, 0);
rev_lvl_dfs(i, 0);
for (int x = 0; x < (int) lvls.size() - 1; x++) {
swap(q[pos[lvls[x]]], q[pos[lvls[x + 1]]]);
}
query(q);
int ans;
cin >> ans;
if (!ans) {
gr[j].push_back(i);
//cout << j << " " << i << endl;
rev_gr[i].push_back(j);
dfs(j);
}
}
}
cout << "end" << endl;
vector <int> resa(n), resb(n);
set <int> q;
vector <int> cnt(n, 0);
for (int i = 0; i < n; i++) {
cnt[i] = gr[i].size();
if (!cnt[i]) {
q.insert(pos[i]);
}
}
int now = 0;
while (!q.empty()) {
int v = *q.begin();
q.erase(v);
resa[v] = now++;
for (int u : rev_gr[p[v]]) {
cnt[u]--;
if (!cnt[u]) {
q.insert(pos[u]);
}
}
}
for (int i = 0; i < n; i++) {
cnt[i] = gr[i].size();
if (!cnt[i]) {
q.insert(pos[i]);
}
}
now = 0;
while (!q.empty()) {
int v = *q.rbegin();
q.erase(v);
resb[v] = now++;
for (int u : rev_gr[p[v]]) {
cnt[u]--;
if (!cnt[u]) {
q.insert(pos[u]);
}
}
}
for (int x : resa) {
cout << x + 1 << " ";
}
cout << endl;
for (int x : resb) {
cout << x + 1 << " ";
}
cout << endl;
}
Compilation message
zagonetka.cpp: In function 'void lvl_dfs(int, int)':
zagonetka.cpp:43:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (h == lvls.size()) {
~~^~~~~~~~~~~~~~
zagonetka.cpp: In function 'void rev_lvl_dfs(int, int)':
zagonetka.cpp:55:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (h == lvls.size()) {
~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
308 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
404 KB |
Output is correct |
| 5 |
Correct |
2 ms |
460 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
664 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
664 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
664 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
