이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
vector<int> P(N);
for (int i = 0; i < N; i++) {
cin >> P[i];
P[i]--;
}
const auto Query = [&](vector<int> a) {
cout << "query";
for (auto i : a) cout << ' ' << i + 1;
cout << endl;
int foo;
cin >> foo;
return foo;
};
vector<int> active;
vector<vector<int>> adj(N);
for (int add = 0; add < N; add++) {
int pos = -1;
for (int i = 0; i < N; i++) {
if (P[i] == add) {
pos = i;
break;
}
}
assert(pos != -1);
for (int _a = int(active.size()) - 1; _a >= 0; _a--) {
int x = active[_a];
vector<int> que = {x};
vector<int> vis(N); vis[x] = 1;
for (int i = 0; i < int(que.size()); i++) {
int u = que[i];
for (auto v : adj[u]) if (!vis[v]) {
vis[v] = 1;
que.emplace_back(v);
}
}
bool found = false;
for (auto y : que) {
if (!adj[y].empty() && adj[y].back() == pos) {
found = true;
break;
}
}
if (found) {
adj[x].emplace_back(pos);
continue;
}
sort(begin(que), end(que), [&](int i, int j) {
return P[i] > P[j];
});
int elem = add;
vector<int> Q = P;
for (auto y : que) {
Q[y] = elem--;
}
Q[pos] = elem--;
vector<int> others;
for (auto y : active) {
if (!vis[y]) {
others.emplace_back(y);
}
}
sort(begin(others), end(others), [&](int i, int j) {
return P[i] > P[j];
});
for (auto y : others) {
Q[y] = elem--;
}
if (!Query(Q)) {
adj[x].emplace_back(pos);
}
}
active.emplace_back(pos);
}
vector<pair<int, int>> edges;
for (int i = 0; i < N; i++) {
for (auto j : adj[i]) {
edges.emplace_back(i, j);
}
}
const auto Solve = [&]() -> vector<int> {
vector<vector<int>> can(N, vector<int>(N));
for (auto [u, v] : edges) {
can[u][v] = 1;
}
for (int k = 0; k < N; k++) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
can[i][j] |= can[i][k] && can[k][j];
}
}
}
int label = 0;
vector<int> res(N, -1);
const auto Dfs = [&](const auto &self, int u) {
if (res[u] != -1) return;
for (int v = 0; v < N; v++) if (can[v][u]) {
self(self, v);
}
res[u] = label++;
};
for (int i = 0; i < N; i++) if (res[i] != -1) {
Dfs(Dfs, i);
}
return res;
};
vector<int> ansSml = Solve();
for (auto &[u, v] : edges) swap(u, v);
vector<int> ansBig = Solve();
for (auto &a : ansBig) a = N - 1 - a;
cout << "end\n";
for (int i = 0; i < N; i++) cout << ansSml[i] + 1 << " \n"[i + 1 == N];
for (int i = 0; i < N; i++) cout << ansBig[i] + 1 << " \n"[i + 1 == N];
cout << flush;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |