Submission #563350

#TimeUsernameProblemLanguageResultExecution timeMemory
563350tranxuanbachSwap (BOI16_swap)C++17
0 / 100
0 ms340 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define endl '\n' #define fi first #define se second #define For(i, l, r) for (auto i = l; i < r; i++) #define ForE(i, l, r) for (auto i = l; i <= r; i++) #define FordE(i, l, r) for (auto i = l; i >= r; i--) #define Fora(v, a) for (auto v: a) #define bend(a) a.begin(), a.end() #define isz(a) ((signed)a.size()) using ll = long long; using ld = long double; using pii = pair <int, int>; using vi = vector <int>; using vpii = vector <pair <int, int>>; using vvi = vector <vector <int>>; const int N = 2e5 + 5; bool debug = 0; int n; int a[N]; int ans[N]; int willgoup[N]; int b[N]; // b[i] will go up and stay at i int valdfs[N]; bool changedfs[N]; int dfs(int i){ // find the lowest index if start at i if (debug) cout << "dfs " << i << endl; if (!changedfs[i]){ return valdfs[i]; } changedfs[i] = 0; if (b[i] == -1 or b[i] == 0){ return (valdfs[i] = i); } if (willgoup[i * 2] == 1){ return (valdfs[i] = dfs(i * 2)); } if (willgoup[i * 2] == 0){ return (valdfs[i] = dfs(i * 2 + 1)); } return (valdfs[i] = min(dfs(i * 2), dfs(i * 2 + 1))); } void dfs_assign(int i, int j){ if (debug) cout << "dfs_assign " << i << ' ' << j << endl; changedfs[i] = 1; if (i == j){ if (i * 2 <= n){ willgoup[i * 2] = 0; } if (i * 2 + 1 <= n){ willgoup[i * 2 + 1] = 0; } b[i] = -1; return; } if (willgoup[i * 2] == 1){ dfs_assign(i * 2, j); return; } if (willgoup[i * 2] == 0){ dfs_assign(i * 2 + 1, j); return; } if (valdfs[i * 2] == j){ willgoup[i * 2] = 1; dfs_assign(i * 2, j); } else{ willgoup[i * 2] = 0; dfs_assign(i * 2 + 1, j); } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("KEK.inp", "r", stdin); // freopen("KEK.out", "w", stdout); cin >> n; ForE(i, 1, n){ cin >> a[i]; } ForE(i, 1, n){ willgoup[i] = -1; b[i] = -1; changedfs[i] = 1; } willgoup[1] = 0; vpii aa; ForE(i, 1, n){ aa.emplace_back(a[i], i); } sort(bend(aa)); Fora(elem, aa){ int val, idx; tie(val, idx) = elem; if (debug) cout << "elem " << val << ' ' << idx << endl; if (willgoup[idx] != 0 and b[idx / 2] == -1){ if (debug) cout << "fix up " << endl; willgoup[idx] = 1; if (idx % 2 == 0){ willgoup[idx + 1] = 0; } b[idx / 2] = idx; ans[idx / 2] = val; continue; } int pos = n + 1, u = -1; if (willgoup[idx] != 1){ int tpos = dfs(idx); if (debug) cout << "case 1 " << tpos << endl; if (pos > tpos){ pos = tpos; u = idx; } } if (idx % 2 == 0 and willgoup[idx] != 0){ int tpos = dfs(idx + 1); if (debug) cout << "case 2 " << tpos << endl; if (pos > tpos){ pos = tpos; u = idx + 1; } } if (debug) cout << "ans " << pos << endl; ans[pos] = val; if (u == idx){ willgoup[idx] = 0; } else{ willgoup[idx] = 1; } dfs_assign(u, pos); while (u != 1){ changedfs[u] = 1; u /= 2; } changedfs[u] = 1; } ForE(i, 1, n){ cout << ans[i] << ' '; } cout << endl; } /* ==================================================+ INPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ OUTPUT: | --------------------------------------------------| --------------------------------------------------| ==================================================+ */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...