This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
typedef long long ll;
typedef long double ld;
const int maxn = 105;
const int mod = 1e9+7;
int n;
vector<int> fg[maxn], rfg[maxn];
int g[maxn][maxn];
int vis[maxn], pos[maxn], qry[maxn], p[maxn], deg[maxn], rdeg[maxn], fdeg[maxn], ans[maxn]; ;
vector<int> vec;
set<int> st;
void dfs(int x, int l, int r){
vis[x]=1;
for(int i = l; i < x; i++){
if(vis[i] || !g[i][x])continue;
dfs(i, l, r);
}
}
bool ask(){
cout << "query ";
for(int i = 1; i <= n; i++)cout << qry[i] << " ";
cout << endl;
bool x;
cin >> x;
cout << endl;
return !x;
}
void fe(int l, int r){
for(int i = 1; i <= n; i++)vis[i]=fdeg[i]=0;
vec.clear();
dfs(r, l, r);
if(vis[l])return;
deque<int> dq;
vector<int> sus;
for(int i = l; i <= r; i++){
for(int j = l; j < i; j++)if(g[j][i])fdeg[i]++;
if(!fdeg[i]){
if(vis[i])dq.push_front(i);
else dq.push_back(i);
}
}
while(!dq.empty()){
auto x = dq.front();
dq.pop_front();
sus.push_back(x);
for(int i = x+1; i <= r; i++)if(g[x][i]){
fdeg[i]--;
if(!fdeg[i]){
if(vis[i])dq.push_front(i);
else dq.push_back(i);
}
}
}
for(int i = 1; i <= n; i++)qry[i]=p[i];
for(int i = l; i <= r; i++){
qry[pos[sus[i-l]]]=i;
}
if(ask()){
g[l][r]=1;
g[r][l]=1;
fg[pos[r]].push_back(pos[l]);
deg[pos[l]]++;
rfg[pos[l]].push_back(pos[r]);
rdeg[pos[r]]++;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
cin >> p[i];
pos[p[i]]=i;
}
for(int i = 1; i <= n; i++){
for(int j = 1; j+i <= n; j++){
fe(j, i+j);
}
}
cout << "end" << endl;
for(int i = 1; i <= n; i++)if(!deg[i])st.insert(i);
for(int i = n; i > 0; i--){
auto x = *prev(st.end());
st.erase(x);
ans[x]=i;
for(auto v: fg[x]){
deg[v]--;
if(!deg[v])st.insert(v);
}
}
for(int i = 1; i <= n; i++)cout << ans[i] << " ";
cout << endl;
for(int i = 1; i <= n; i++){
if(!rdeg[i])st.insert(i);
}
for(int i = 1; i <= n; i++){
auto x = *prev(st.end());
st.erase(x);
ans[x]=i;
for(auto v: rfg[x]){
rdeg[v]--;
if(!rdeg[v])st.insert(v);
}
}
for(int i = 1; i <= n; i++)cout << ans[i] << " ";
cout << endl;
}
/*
1 3 5 4 2
*/
# | 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... |