제출 #970851

#제출 시각아이디문제언어결과실행 시간메모리
970851jcelinZagonetka (COI18_zagonetka)C++14
100 / 100
222 ms744 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> ii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<ll> vll; typedef vector<pll> vpll; #define PB push_back #define PF push_front #define PPB pop_back #define PPF pop_front #define X first #define Y second #define MP make_pair #define all(x) (x).begin(), (x).end() const int mod = 998244353; const int inf = 1e9 + 7; const ll INF = 1e18 + 7; const int logo = 20; const int MAXN = 107; const int off = 1 << logo; const int trsz = off << 1; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, -1, 1}; int brid[MAXN][MAXN], p[MAXN], n; vi topo, vls, g[MAXN]; vii edg; int in[MAXN]; bool bio[MAXN]; /* 14 10 13 9 1 5 6 7 4 12 11 14 3 8 2 3 13 10 6 2 4 5 */ bool provjera(){ for(auto &x : edg){ if(vls[x.X] >= vls[x.Y]) return 0; } return 1; } bool query(){ //return provjera(); cout << "query "; for(auto &x : vls) cout << x << " "; cout << endl; bool x; cin >> x; return x; } void make_topo(){ topo.clear(); for(int i=1; i<=n; i++) g[i].clear(), in[i] = 0; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++) if(brid[i][j]) g[i].PB(j), in[j]++; } vi s; for(int i=1; i<=n; i++) if(!in[i]) s.PB(i); while(s.size()){ int u = s.back(); topo.PB(u); s.PPB(); for(auto &x : g[u]){ if(--in[x] == 0) s.PB(x); } } vls.resize(n); for(int i=0; i<n; i++) vls[topo[i] - 1] = i + 1; } void dfs(int u){ if(bio[u]) return; bio[u] = 1; for(int i=1; i<=n; i++) if(brid[u][i] == 2) dfs(i); } bool postoji(int x, int y){ fill(bio, bio + n + 1, 0); dfs(x); return bio[y]; } bool bridcheck(){ make_topo(); int na = 0, nb = 0; for(int i=n-1; i>=0; i--){ if(na) break; for(int j=i; j<n; j++){ if(na) break; int a = topo[i], b = topo[j]; if(brid[a][b] != 1) continue; if(postoji(a, b)) brid[a][b] = 2; else na = a, nb = b; } } if(na == 0 and nb == 0) return 0; brid[na][nb] = 0; brid[nb][na] = 1; make_topo(); brid[nb][na] = 0; if(!query()) brid[na][nb] = 2; else brid[na][nb] = 0; return 1; } int ans[MAXN]; void najm(set<int> pos, int lo, int hi){ if(pos.empty()) return; int mini = *pos.begin(); set<int> a; for(auto &x : g[mini]) if(pos.find(x) != pos.end()) a.insert(x); for(auto &x : a) pos.erase(x); if(a.empty()){ pos.erase(mini); ans[mini] = lo; najm(pos, lo + 1, hi); }else{ najm(a, lo, lo + a.size() - 1); najm(pos, lo + a.size(), hi); } } void najv(set<int> pos, int lo, int hi){ if(pos.empty()) return; int mini = *pos.begin(); set<int> a; for(auto &x : g[mini]) if(pos.find(x) != pos.end()) a.insert(x); for(auto &x : a) pos.erase(x); if(a.empty()){ pos.erase(mini); ans[mini] = hi; najv(pos, lo, hi - 1); }else{ najv(a, hi - a.size() + 1, hi); najv(pos, lo, hi - a.size()); } } void solve(){ cin >> n; for(int i=1; i<=n; i++) cin >> p[i]; for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++) if(p[i] < p[j]) brid[i][j] = 1; } while(bridcheck()); for(int i=1; i<=n; i++) g[i].clear(); for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ if(brid[i][j]) g[j].PB(i); } } cout << "end" << endl; set<int> cur; for(int i=1; i<=n; i++) cur.insert(i); najm(cur, 1, n); for(int i=1; i<=n; i++) cout << ans[i] << " "; cout << "\n"; for(int i=1; i<=n; i++) g[i].clear(); for(int i=1; i<=n; i++){ for(int j=1; j<=n; j++){ if(brid[i][j]) g[i].PB(j); } } najv(cur, 1, n); for(int i=1; i<=n; i++) cout << ans[i] << " "; cout << "\n"; } int main(){ solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...