#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= l; --i)
#define ALL(x) (x).begin(), (x).end()
using i64 = long long;
void answer(vector<int> P, vector<int> Q) {
cout << "end" << endl;
rep(i, 0, (int)P.size()) cout << P[i] + 1 << (i == (int)P.size() - 1 ? '\n' : ' ');
rep(i, 0, (int)Q.size()) cout << Q[i] + 1 << (i == (int)Q.size() - 1 ? '\n' : ' ');
cout << flush;
}
bool ask(vector<int> P) {
cout << "query ";
rep(i, 0, (int)P.size()) {
cout << P[i] + 1 << (i == (int)P.size() - 1 ? '\n' : ' ');
}
cout << flush;
int res;
cin >> res;
return res ? true : false;
}
void main_() {
int N;
cin >> N;
vector<int> P(N);
for (auto &e : P) {
cin >> e;
--e;
}
vector<int> rP(N);
rep(i, 0, N) rP[P[i]] = i;
vector<vector<int>> C(N);
auto makeCut = [&](int a, int b) -> pair<vector<int>, vector<int>> {
vector<int> x;
vector<bool> isUsed(N);
queue<int> que;
que.push(a);
isUsed[a] = true;
while (not que.empty()) {
const auto f = que.front();
que.pop();
if (P[f] > P[b]) continue;
x.push_back(f);
for (const auto t : C[f]) {
if (isUsed[t]) continue;
isUsed[t] = true;
que.push(t);
}
}
if (find(ALL(x), b) != x.end()) {
return {{}, {}};
} else {
vector<int> y;
rep(i, P[a], P[b] + 1) {
if (find(ALL(x), rP[i]) == x.end()) y.push_back(rP[i]);
}
return {x, y};
}
};
rep(w, 1, N) {
rep(lx, 0, N - w) {
int r = lx + w;
int l = lx;
const auto [x, y] = makeCut(rP[l], rP[r]);
if (x.empty()) {
C[rP[l]].push_back(rP[r]);
} else {
// query
auto p = P;
// const int a = (int)x.size(), b = (int)y.size();
int v = l;
for (const auto e : y) {
p[e] = v++;
}
for (const auto e : x) {
p[e] = v++;
}
const auto res = ask(p);
if (not res) {
C[rP[l]].push_back(rP[r]);
}
}
}
}
vector<vector<int>> rC(N);
rep(i, 0, N) {
for (const auto t : C[i]) {
rC[t].push_back(i);
}
}
vector<int> ansA, ansB;
{
vector<int> val(N, -1);
int nowVal = 0;
auto mkMin = [&](auto &&self, const int v) -> void {
assert(val[v] == -1);
vector<int> vs;
queue<int> que;
que.push(v);
vector<bool> isUsed(N);
isUsed[v] = true;
while (not que.empty()) {
const auto f = que.front();
que.pop();
vs.push_back(f);
for (const auto t : rC[f]) {
if (isUsed[t]) continue;
if (val[t] != -1) continue;
isUsed[t] = true;
que.push(t);
}
}
vs.erase(find(ALL(vs), v));
while (not vs.empty()) {
const int mn = *min_element(ALL(vs));
self(self, mn);
vector<int> nextVs;
for (const auto e : vs) if (val[e] == -1) nextVs.push_back(e);
vs = move(nextVs);
}
val[v] = nowVal++;
};
rep(i, 0, N) {
if (val[i] == -1) {
mkMin(mkMin, i);
}
}
ansA = val;
}
{
vector<int> val(N, -1);
int nowVal = N - 1;
auto mkMax = [&](auto &&self, const int v) -> void {
assert(val[v] == -1);
vector<int> vs;
queue<int> que;
que.push(v);
vector<bool> isUsed(N);
isUsed[v] = true;
while (not que.empty()) {
const auto f = que.front();
que.pop();
vs.push_back(f);
for (const auto t : C[f]) {
if (isUsed[t]) continue;
if (val[t] != -1) continue;
isUsed[t] = true;
que.push(t);
}
}
vs.erase(find(ALL(vs), v));
while (not vs.empty()) {
const int mn = *min_element(ALL(vs));
self(self, mn);
vector<int> nextVs;
for (const auto e : vs) if (val[e] == -1) nextVs.push_back(e);
vs = move(nextVs);
}
val[v] = nowVal--;
};
rep(i, 0, N) {
if (val[i] == -1) {
mkMax(mkMax, i);
}
}
ansB = val;
}
answer(ansA, ansB);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
main_();
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
448 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
452 KB |
Output is correct |
| 5 |
Correct |
0 ms |
452 KB |
Output is correct |
| 6 |
Correct |
1 ms |
448 KB |
Output is correct |
| 7 |
Correct |
0 ms |
452 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
344 KB |
Output is correct |
| 2 |
Correct |
16 ms |
344 KB |
Output is correct |
| 3 |
Correct |
16 ms |
452 KB |
Output is correct |
| 4 |
Correct |
17 ms |
344 KB |
Output is correct |
| 5 |
Correct |
4 ms |
344 KB |
Output is correct |
| 6 |
Correct |
19 ms |
448 KB |
Output is correct |
| 7 |
Correct |
3 ms |
612 KB |
Output is correct |
| 8 |
Correct |
3 ms |
344 KB |
Output is correct |
| 9 |
Correct |
15 ms |
432 KB |
Output is correct |
| 10 |
Correct |
7 ms |
456 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
456 KB |
Output is correct |
| 2 |
Correct |
1 ms |
448 KB |
Output is correct |
| 3 |
Correct |
3 ms |
452 KB |
Output is correct |
| 4 |
Correct |
2 ms |
700 KB |
Output is correct |
| 5 |
Correct |
1 ms |
448 KB |
Output is correct |
| 6 |
Correct |
2 ms |
708 KB |
Output is correct |
| 7 |
Correct |
2 ms |
456 KB |
Output is correct |
| 8 |
Correct |
3 ms |
444 KB |
Output is correct |
| 9 |
Correct |
3 ms |
456 KB |
Output is correct |
| 10 |
Correct |
1 ms |
448 KB |
Output is correct |
| 11 |
Correct |
2 ms |
452 KB |
Output is correct |
| 12 |
Correct |
3 ms |
448 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
46 ms |
452 KB |
Output is correct |
| 2 |
Correct |
46 ms |
344 KB |
Output is correct |
| 3 |
Correct |
40 ms |
444 KB |
Output is correct |
| 4 |
Correct |
7 ms |
716 KB |
Output is correct |
| 5 |
Correct |
10 ms |
460 KB |
Output is correct |
| 6 |
Correct |
10 ms |
712 KB |
Output is correct |
| 7 |
Correct |
13 ms |
456 KB |
Output is correct |
| 8 |
Correct |
19 ms |
704 KB |
Output is correct |
| 9 |
Correct |
16 ms |
708 KB |
Output is correct |
| 10 |
Correct |
40 ms |
688 KB |
Output is correct |
| 11 |
Correct |
35 ms |
440 KB |
Output is correct |
| 12 |
Correct |
34 ms |
444 KB |
Output is correct |
| 13 |
Correct |
43 ms |
692 KB |
Output is correct |
| 14 |
Correct |
42 ms |
456 KB |
Output is correct |
| 15 |
Correct |
40 ms |
444 KB |
Output is correct |
| 16 |
Correct |
40 ms |
708 KB |
Output is correct |
