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>
#define FOR(i,a) for(int i=0;i<a;i++)
#define FOR1(i,a) for(int i=1;i<=a;i++)
#define db(a) printf("<%d> ",a)
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb emplace_back
#define p emplace
#define ii pair<int,int>
#define ll long long
#define rf() freopen("_working/input.in","r",stdin)
#define pf() freopen("_working/output.out","w+",stdout)
using namespace std;
const int INF=1e9;
int tab[105];
int x[105];
int visit[105];
int edge[105][105];
vector<int> e[105];
int deg[105];
int n;
int query(){
FOR(i,n){
x[tab[i]-1]=i+1;
}
printf("query ");
for(int i=0;i<n;i++){
printf("%d ",x[i]);
}
cout<<endl;
int x;
cin>>x;
return !x;
}
void find(int i){
visit[tab[i]]=1;
while(i>0&&edge[tab[i]][tab[i-1]]!=1){
swap(tab[i],tab[i-1]);
if(edge[tab[i-1]][tab[i]]==-1){
i--;
continue;
}
if(query()){
swap(tab[i],tab[i-1]);
edge[tab[i]][tab[i-1]]=1;
find(i-1);
continue;
}
i--;
}
}
int main(){
cin>>n;
FOR(i,n){
cin>>x[i];
tab[x[i]-1]=i+1;
}
FOR(i,n){
for(int j=i-1;j>=0;j--)edge[tab[j]][tab[i]]=-1;
}
while(visit[tab[n-1]]!=1){
find(n-1);
}
printf("end");
cout<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(edge[i][j]==1){
//printf("<%d,%d>\n",i,j);
e[j].pb(i);
}
}
}
priority_queue<int,vector<int>,greater<int>> q1;
FOR1(i,n){
for(auto j:e[i])deg[j]++;
}
int cnt=1;
FOR1(i,n)if(deg[i]==0)q1.p(i);
while(!q1.empty()){
tab[q1.top()]=cnt++;
int u = q1.top();
q1.pop();
for(auto v:e[u]){
deg[v]--;
if(deg[v]==0){q1.p(v);}
}
}
FOR1(i,n)printf("%d ",tab[i]);
cout<<endl;
cnt = 1;
FOR1(i,n)deg[i]=0;
priority_queue<int> q;
FOR1(i,n){
for(auto j:e[i])deg[j]++;
}
FOR1(i,n)if(deg[i]==0)q.p(i);
while(!q.empty()){
tab[q.top()]=cnt++;
int u = q.top();
q.pop();
for(auto v:e[u]){
deg[v]--;
if(deg[v]==0){q.p(v);}
}
}
FOR1(i,n)printf("%d ",tab[i]);
cout<<endl;
}
# | 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... |