이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define all(arr) (arr).begin(), (arr).end()
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
// #define endl '\n'
const int N = 500;
int g[N][N]; // g[i][j] = 1 -> p[i] > p[j]
int ask(vector<int> p){
cout << "query ";
for (auto i : p) cout << i + 1 << " ";
cout << endl;
int ans;
cin >> ans;
return ans;
}
void answer(vector<int> p, vector<int> q){
cout << "end" << endl;
for (auto i : p) cout << i + 1 << " ";
cout << endl;
for (auto i : q) cout << i + 1 << " ";
cout << endl;
}
int n;
vector<int> lexmin, lexmax;
int cur = 0;
void dfsmin(int i){
if (lexmin[i] != -1) return;
for (int j = 0; j < n; j++){
if (g[i][j]) dfsmin(j);
}
lexmin[i] = cur++;
}
void dfsmax(int i){
if (lexmax[i] != -1) return;
for (int j = 0; j < n; j++){
if (g[j][i]) dfsmax(j);
}
lexmax[i] = cur--;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
// cout.precision(20);
cin >> n;
vector<int> p(n), pos(n);
for (auto &i : p){
cin >> i;
i--;
}
for (int i = 0; i < n; i++) pos[p[i]] = i;
for (int i = 0; i < n; i++){
// find all states with pos[i]
vector<int> nocare, care{pos[i]};
for (int j = i + 1; j < n; j++){
vector<int> q = p;
int cur = i;
for (auto k : nocare) q[k] = cur++;
q[pos[j]] = cur++;
for (auto k : care) q[k] = cur++;
g[pos[j]][pos[i]] = !ask(q);
(g[pos[j]][pos[i]]? care : nocare).pb(pos[j]);
}
}
lexmin.assign(n, -1);
for (int i = 0; i < n; i++) dfsmin(i);
lexmax.assign(n, -1);
cur = n - 1;
for (int i = 0; i < n; i++) dfsmax(i);
answer(lexmin, lexmax);
}
# | 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... |