Submission #672116

#TimeUsernameProblemLanguageResultExecution timeMemory
672116LoboSwap (BOI16_swap)C++17
100 / 100
69 ms35752 KiB
#include<bits/stdc++.h> using namespace std; const long long inf = (long long) 1e18 + 10; const int inf1 = (int) 1e9 + 10; #define int long long #define dbl long double #define endl '\n' #define sc second #define fr first #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() const int maxn = 4e5+10; int n, p[maxn], id[maxn], ans[maxn], up[maxn]; set<int> st[maxn]; void solve() { cin >> n; for(int i = 1; i <= n; i++) { cin >> p[i]; st[i].insert(p[i]); } st[0].insert(n+1); for(int i = 1; i <= n; i++) { int lc = 2*i; if(lc > n) lc = 0; int rc = 2*i+1; if(rc > n) rc = 0; int a = inf; int k = i; while(k != 0) { if(st[k].size()) a = min(a, *st[k].begin()); if(k/2 == 0 || ((up[k/2]&(1<<(k&1))) == 0)) break; k/= 2; } int b = *st[lc].begin(); int c = *st[rc].begin(); ans[i] = min({a,b,c}); if(min({a,b,c}) == a) { k = i; while(k != 0) { if(st[k].count(a)) { st[k].erase(a); break; } up[k/2]^= (1<<(k&1)); k/= 2; } up[i] = 0; } else if(min({a,b,c}) == b) { up[i] = 1; st[2*i].clear(); } else { st[i].insert(*st[2*i].begin()); up[i] = 3; st[2*i].clear(); st[2*i+1].clear(); } } for(int i = 1; i <= n; i++) { cout << ans[i] << " "; }cout << endl; } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); // freopen("in.in", "r", stdin); // freopen("out.out", "w", stdout); int tt = 1; // cin >> tt; while(tt--) { solve(); } }
#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...