#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
bool mini(auto &x, const auto &y) {
if (y < x) {
x = y;
return 1;
}
return 0;
}
bool maxi(auto &x, const auto &y) {
if (y > x) {
x = y;
return 1;
}
return 0;
}
void run();
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
run();
return 0;
}
const int N = 101;
int n;
vector<int> p;
int pos[N];
bool e[N][N];
bool ask(vector<int> q) {
cout << "query ";
for (int i : q) {
cout << i << " ";
}
cout << endl;
int x;
cin >> x;
return x;
}
bool conn(int u, int v) {
return e[u][v] || e[v][u];
}
bool cool[N];
bool vis[N];
void dfs(int v, vector<int> &st) {
vis[v] = 1;
rep(u, 0, n) {
if (!cool[u] || !e[v][u] || vis[u]) {
continue;
}
dfs(u, st);
}
st.pb(v);
}
void run() {
cin >> n;
p.resize(n);
rep(i, 0, n) {
cin >> p[i];
e[i][i] = 1;
pos[p[i]] = i;
}
rep(len, 1, n) {
rep(i, 1, n + 1) {
int j = i + len;
if (j > n) {
break;
}
int a = pos[i];
int b = pos[j];
if (conn(a, b)) {
continue;
}
vector<int> A, B, C;
memset(cool, 0, sizeof cool);
memset(vis, 0, sizeof vis);
vector<int> yeah;
rep(t, 0, n) {
if (i <= p[t] && p[t] <= j) {
if (conn(a, t)) {
assert(!conn(b, t));
A.pb(t);
} else if (conn(b, t)) {
B.pb(t);
} else {
C.pb(t);
}
cool[t] = 1;
yeah.pb(p[t]);
}
}
sort(all(yeah));
vector<int> SA, SB, SC;
for (int v : A) {
if (!vis[v]) {
dfs(v, SA);
}
}
for (int v : B) {
if (!vis[v]) {
dfs(v, SB);
}
}
for (int v : C) {
if (!vis[v]) {
dfs(v, SC);
}
}
vector<int> q = p;
for (int v : SA) {
q[v] = yeah.back();
yeah.pop_back();
}
for (int v : SB) {
q[v] = yeah.back();
yeah.pop_back();
}
for (int v : SC) {
q[v] = yeah.back();
yeah.pop_back();
}
if (!ask(q)) {
e[a][b] = 1;
rep(iter, 0, 2) {
rep(u, 0, n) {
rep(v, 0, n) {
e[u][v] |= e[u][a] && e[a][v];
}
}
rep(u, 0, n) {
rep(v, 0, n) {
e[u][v] |= e[u][b] && e[b][v];
}
}
}
}
}
}
cout << "end" << endl;
/*rep(i, 0, n) {
rep(j, 0, n) {
if (e[i][j] && i != j) {
cerr << i << " " << j << endl;
}
}
}*/
{
vector<int> res(n);
function<void(vector<int> pos, int ptr)> f = [&] (vector<int> pos, int ptr) {
if (!sz(pos)) {
return;
}
vector<int> pos_sh = pos;
pos_sh.erase(pos_sh.begin());
int v = pos[0];
if (!res[v]) {
vector<int> nxt;
for (int p : pos_sh) {
if (!res[p] && e[p][v]) {
nxt.pb(p);
}
}
res[v] = ptr + sz(nxt);
f(nxt, ptr);
ptr += (1 + sz(nxt));
}
f(pos_sh, ptr);
};
vector<int> pos(n);
rep(i, 0, n) {
pos[i] = i;
}
f(pos, 1);
for (int v : res) {
cout << v << " ";
}
cout << endl;
}
{
vector<int> res(n);
function<void(vector<int> pos, int ptr)> f = [&] (vector<int> pos, int ptr) {
if (!sz(pos)) {
return;
}
vector<int> pos_sh = pos;
pos_sh.erase(pos_sh.begin());
int v = pos[0];
if (!res[v]) {
vector<int> nxt;
for (int p : pos_sh) {
if (!res[p] && e[v][p]) {
nxt.pb(p);
}
}
res[v] = ptr - sz(nxt);
f(nxt, ptr);
ptr -= (1 + sz(nxt));
}
f(pos_sh, ptr);
};
vector<int> pos(n);
rep(i, 0, n) {
pos[i] = i;
}
f(pos, n);
for (int v : res) {
cout << v << " ";
}
cout << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
436 KB |
Output is correct |
| 3 |
Correct |
2 ms |
516 KB |
Output is correct |
| 4 |
Correct |
2 ms |
516 KB |
Output is correct |
| 5 |
Correct |
2 ms |
516 KB |
Output is correct |
| 6 |
Correct |
2 ms |
516 KB |
Output is correct |
| 7 |
Correct |
2 ms |
516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
528 KB |
Output is correct |
| 2 |
Correct |
35 ms |
640 KB |
Output is correct |
| 3 |
Correct |
43 ms |
640 KB |
Output is correct |
| 4 |
Correct |
51 ms |
640 KB |
Output is correct |
| 5 |
Correct |
9 ms |
640 KB |
Output is correct |
| 6 |
Correct |
51 ms |
640 KB |
Output is correct |
| 7 |
Correct |
8 ms |
640 KB |
Output is correct |
| 8 |
Correct |
10 ms |
640 KB |
Output is correct |
| 9 |
Correct |
37 ms |
640 KB |
Output is correct |
| 10 |
Correct |
20 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
640 KB |
Output is correct |
| 2 |
Correct |
2 ms |
640 KB |
Output is correct |
| 3 |
Correct |
6 ms |
640 KB |
Output is correct |
| 4 |
Correct |
6 ms |
640 KB |
Output is correct |
| 5 |
Correct |
4 ms |
640 KB |
Output is correct |
| 6 |
Correct |
5 ms |
640 KB |
Output is correct |
| 7 |
Correct |
5 ms |
640 KB |
Output is correct |
| 8 |
Correct |
5 ms |
700 KB |
Output is correct |
| 9 |
Correct |
7 ms |
700 KB |
Output is correct |
| 10 |
Correct |
3 ms |
700 KB |
Output is correct |
| 11 |
Correct |
5 ms |
700 KB |
Output is correct |
| 12 |
Correct |
6 ms |
700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
700 KB |
Output is correct |
| 2 |
Correct |
135 ms |
716 KB |
Output is correct |
| 3 |
Correct |
106 ms |
716 KB |
Output is correct |
| 4 |
Correct |
7 ms |
716 KB |
Output is correct |
| 5 |
Correct |
8 ms |
716 KB |
Output is correct |
| 6 |
Correct |
8 ms |
716 KB |
Output is correct |
| 7 |
Correct |
34 ms |
716 KB |
Output is correct |
| 8 |
Correct |
73 ms |
716 KB |
Output is correct |
| 9 |
Correct |
52 ms |
716 KB |
Output is correct |
| 10 |
Correct |
132 ms |
716 KB |
Output is correct |
| 11 |
Correct |
114 ms |
716 KB |
Output is correct |
| 12 |
Correct |
110 ms |
716 KB |
Output is correct |
| 13 |
Correct |
134 ms |
716 KB |
Output is correct |
| 14 |
Correct |
119 ms |
720 KB |
Output is correct |
| 15 |
Correct |
145 ms |
720 KB |
Output is correct |
| 16 |
Correct |
130 ms |
720 KB |
Output is correct |
