Submission #677026

#TimeUsernameProblemLanguageResultExecution timeMemory
677026dooompySwap (BOI16_swap)C++17
100 / 100
235 ms28628 KiB
#include "bits/stdc++.h" using namespace std; void abc() {cout << endl;} template <typename T, typename ...U> void abc(T a, U ...b) { cout << a << ' ', abc(b...); } template <typename T> void printv(T l, T r) { while (l != r) cout << *l << " \n"[++l == r]; } template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) { return o >> a.first >> a.second; } template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) { return o << '(' << a.first << ", " << a.second << ')'; } template <typename T> ostream& operator << (ostream& o, vector<T> a) { bool is = false; for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;} return o << '}'; } #ifdef local #define test(args...) abc("[" + string(#args) + "]", args) #else #define test(args...) void(0) #endif using ll = long long; int v[200005]; map<pair<int, int>, int> stored; int n; int dp(int loc, int val) { if (stored.count({loc, val})) { return stored[{loc, val}]; } int r = loc * 2 + 1; int l = loc * 2; if (l > n && r > n) { return stored[{loc, val}] = loc; } if (r > n) { if (val < v[l]) return loc; return stored[{loc, val}] = dp(l, val); } if (val < min(v[l], v[r])) { return stored[{loc, val}] = loc; } if (v[l] < v[r]) { return stored[{loc, val}] = dp(l, val); } int mn = min(v[l], val); if (dp(l, mn) < dp(r, mn)) { if (mn == val) { return stored[{loc, val}] = dp(l, val); } else { return stored[{loc, val}] = dp(r, val); } } else { if (mn != val) { return stored[{loc, val}] = dp(l, val); } else { return stored[{loc, val}] = dp(r, val); } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("", "r", stdin); // freopen("", "w", stdout); cin >> n; for (int i = 1; i <= n; i++) cin >> v[i]; for (int i = 1; i <= n; i++) { int l = i * 2, r = i * 2 + 1; if (l > n && r > n) { // cant rly do anything continue; } if (r > n && l <= n) { if (v[l] < v[i]) { swap(v[l], v[i]); } continue; } if (v[l] == min({v[l], v[r], v[i]})) { swap(v[l], v[i]); continue; } if (v[r] == min({v[l], v[r], v[i]})) { swap(v[i], v[r]); int mn = min(v[l], v[r]), mx = max(v[l], v[r]); if (dp(l, mn) < dp(r, mn)) { tie(v[l], v[r]) = {mn, mx}; } else tie(v[l], v[r]) = {mx, mn}; } } for (int i = 1; i <= n; i++) { cout << v[i] << " "; } }
#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...