Submission #276055

#TimeUsernameProblemLanguageResultExecution timeMemory
276055PKhingZagonetka (COI18_zagonetka)C++14
9 / 100
90 ms384 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...