#include "bits/stdc++.h"
using namespace std;
int n;
vector <int> p;
bool query(vector <int> v) {
vector <int> p (v.size());
for(size_t i = 0; i < v.size(); i++) {
p[v[i]] = i;
}
cout << "query";
for(auto i : p) {
cout << " " << (i+1);
}
cout << endl;
int ans;
cin >> ans;
return ans;
}
vector <int> g[111];
vector <int> rev[111];
bool vis[111];
void dfs(int x) {
vis[x] = true;
for(auto i : g[x]) {
if(!vis[i]) {
dfs(i);
}
}
}
int mx[111];
int mn[111];
int in[111];
void dp(int x) {
mn[x] = x;
for(auto i : g[x]) {
if(!vis[i]) dp(i);
mn[x] = min(mn[x], mn[i]);
}
}
void fn(int x) {
mn[x] = x;
for(auto i : rev[x]) {
if(!vis[i]) fn(i);
mn[x] = min(mn[x], mn[i]);
}
}
int main(int argc, char const *argv[])
{
cin >> n;
p.resize(n);
for(int i = 0; i < n; i++) {
int x;
cin >> x;
p[x-1] = i;
}
int cnt = 0;
for(int i = n-1; i >= 0; i--) {
memset(vis, false, sizeof vis);
for(int j = i+1; j < n; j++) {
if(vis[p[j]] == false) {
// cout << p[i]+1 << " with " << p[j]+1 << endl;
vector <int> tmp;
for(int k = 0; k < i; k++) {
tmp.emplace_back(p[k]);
}
for(int k = i+1; k <= j; k++) {
if(vis[p[k]] == false) {
tmp.emplace_back(p[k]);
}
}
tmp.emplace_back(p[i]);
for(int k = i+1; k < n; k++) {
if(vis[p[k]] == false && k <= j) continue;
tmp.emplace_back(p[k]);
}
if(query(tmp) == 0) {
g[p[i]].emplace_back(p[j]);
rev[p[j]].emplace_back(p[i]);
dfs(p[j]);
cerr << p[i]+1 << ' ' << p[j]+1 << endl;
++cnt;
}
}
}
}
cerr << cnt << endl;
cout << "end" << endl;
typedef pair <int, int> pii;
priority_queue <pii> P;
priority_queue <pii, vector <pii>, greater <pii>> Q;
vector <int> small, big;
memset(in, 0, sizeof in);
for(int i = 0; i < n; i++) {
for(int j : g[i]) {
++in[j];
}
}
memset(vis, false, sizeof vis);
for(int i = 0; i < n; i++) {
if(!vis[i]) {
dp(i);
}
}
for(int i = 0; i < n; i++) {
if(in[i] == 0) {
Q.push(pii(mn[i], i));
}
}
while(!Q.empty()) {
int x = Q.top().second;
Q.pop();
small.push_back(x);
for(int i : g[x]) {
--in[i];
if(in[i] == 0) {
Q.push(pii(mn[i], i));
}
}
}
memset(in, 0, sizeof in);
for(int i = 0; i < n; i++) {
for(int j : rev[i]) {
++in[j];
}
}
memset(vis, false, sizeof vis);
for(int i = 0; i < n; i++) {
if(!vis[i]) {
fn(i);
}
}
for(int i = 0; i < n; i++) {
if(in[i] == 0) {
Q.push(pii(mn[i], i));
}
}
while(!Q.empty()) {
int x = Q.top().second;
Q.pop();
big.push_back(x);
for(int i : rev[x]) {
--in[i];
if(in[i] == 0) {
Q.push(pii(mn[i], i));
}
}
}
reverse(big.begin(), big.end());
vector <int> ans (n);
for(int i = 0; i < n; i++) {
ans[small[i]] = i;
}
for(int i : ans) {
cout << i+1 << ' ';
}
cout << endl;
for(int i = 0; i < n; i++) {
ans[big[i]] = i;
}
for(int i : ans) {
cout << i+1 << ' ';
}
cout << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
248 KB |
not a valid command |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
308 KB |
not a valid command |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
308 KB |
not a valid command |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
344 KB |
not a valid command |
| 2 |
Halted |
0 ms |
0 KB |
- |
