Submission #640654

#TimeUsernameProblemLanguageResultExecution timeMemory
640654socpiteZagonetka (COI18_zagonetka)C++14
0 / 100
61 ms336 KiB
#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], 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]=deg[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])deg[i]++; if(!deg[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]){ deg[i]--; if(!deg[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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...