#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Mod = 1000000007LL;
const int N = 1e2 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;
ll p[N], q[N], ind[N];
vector<ll> G[N], top;
ll L, R;
int mk[N], n;
void DFS(int u){
mk[u] = 1;
for(auto adj : G[u]) if(!mk[adj] && L <= p[adj] && p[adj] <= R) DFS(adj);
top.pb(u);
}
bool Val(int x){
memset(mk, 0, sizeof mk);
top.clear();
for(int i = L; i <= R; i++){
if(!mk[ind[i]]){
DFS(ind[i]);
}
}
reverse(all(top));
memcpy(q, p, sizeof p);
//cerr << "$$ " << top.size() << '\n';
//assert(top.size() == x);
for(int i = L; i <= R; i++)
q[top[i-L]] = i;
cout << "query";
for(int i = 1; i <= n; i++) cout << " " << q[i];
cout << endl;
int res;
//res = (q[1] > q[2]) && (q[3] < q[4]);
cin >> res;
//debug(res);
return res;
}
int g[N][N];
int mx[N], mn[N];
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> p[i];
ind[p[i]] = i;
}
for(int i = 2; i <= n; i++){
for(int j = i - 1; j > 0; j--){
L = j;
R = i;
G[ind[i]].pb(ind[j]);
int rs = Val(i);
G[ind[i]].pop_back();
if(!rs){
//cerr << "!! " << ind[j] << " " << ind[i] << '\n';
G[ind[j]].pb(ind[i]);
}
}
}
for(int i = 1; i <= n; i++){
for(auto x : G[i]){
g[i][x] = 1;
}
}
vector<int> vv(n);
vector<int> Mn, Mx;
iota(all(vv), 1);
do {
int fl = 1;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if((vv[i] > vv[j]) && (g[i+1][j+1])) fl = 0;
}
}
if(fl) Mx = vv;
} while(next_permutation(all(vv)));
top.clear();
memset(mk,0,sizeof mk);
cout << "end" << endl;
//for(auto al : Mn) cout << al << " ";
//cout << '\n';
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
for(int k = 1; k <= n; k ++)
if(g[j][i] && g[i][k])
g[j][k] = 1;
iota(mn, mn + N, 0);
vector<ll> v;
for(int i = 1; i <= n; i++){
int idx = -1;
for(int k = 1; k <= n; k++) if(mn[k] == i) idx = k;
int L = idx, R = idx;
while((L > 0) && (mn[L] >= i)) L--;
while((R <= n) && (mn[R] >= i)) R++;
v.clear();
for(int j = L + 1; j < R; j++)
if(g[mn[j]][i]) v.pb(mn[j]);
v.pb(i);
for(int j = L + 1; j < R; j++)
if(!g[mn[j]][i] && j != idx) v.pb(mn[j]);
for(int j = L + 1; j < R; j++)
mn[j] = v[j - L - 1];
}
for(int i = 1; i <= n; i++)
for(int k = 1; k <= n; k++) if(mn[k] == i) cout << k << " ";
cout << endl;
for(auto al : Mx) cout << al << " ";
cout << endl;
return 0;
}
/*
4
3 2 1 4
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
4 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
432 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3028 ms |
392 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3059 ms |
384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3069 ms |
384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
