Submission #228779

#TimeUsernameProblemLanguageResultExecution timeMemory
228779quocnguyen1012Swap (BOI16_swap)C++14
100 / 100
880 ms3832 KiB
#include<bits/stdc++.h> typedef long long ll; typedef long double lld; using namespace std; #define endl "\n" #define fi first #define se second #define MEMS(a,b) memset(a,b,sizeof(a)) #define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define __ freopen("input.txt","r",stdin);freopen("output.txt","w",stdout); #define all(c) c.begin(),c.end() #define pii pair<int, int> mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { uniform_int_distribution<int> uid(l, r); return uid(rng); } #define tr(...) cout<<__FUNCTION__<<' '<<__LINE__<<" = ";trace(#__VA_ARGS__, __VA_ARGS__) template<typename S, typename T> ostream& operator<<(ostream& out,pair<S,T> const& p){out<<'('<<p.fi<<", "<<p.se<<')';return out;} template<typename T> ostream& operator<<(ostream& out,vector<T> const& v){ ll l=v.size();for(ll i=0;i<l-1;i++)out<<v[i]<<' ';if(l>0)out<<v[l-1];return out;} template <typename T> ostream &operator<<(ostream &out, set<T> const &v) { for (auto i = v.begin(); i != v.end(); i++) out << (*i) << ' '; return out; } template <typename T> ostream &operator<<(ostream &out, multiset<T> const &v) { for (auto i = v.begin(); i != v.end(); i++) out << (*i) << ' '; return out; } template <typename T, typename V> ostream &operator<<(ostream &out, map<T, V> const &v) { for (auto i = v.begin(); i != v.end(); i++) out << "\n" << (i->first) << ":" << (i->second); return out; } template<typename T> void trace(const char* name, T&& arg1){cout<<name<<" : "<<arg1<<endl;} template<typename T, typename... Args> void trace(const char* names, T&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ',');cout.write(names, comma-names)<<" : "<<arg1<<" | ";trace(comma+1,args...);} // #define int ll const int N = 2e5 + 10; const int inf = 1e9 + 1; int n, arr[N]; map<pii, int> dp; int f(int ind, int val) { if (dp.count({ind, val})) return dp[{ind, val}]; // int &ans = dp[{ind, val}]; int ans = 0; if (2 * ind > n) { return ans = ind; } if ((2 * ind + 1) > n) { if (arr[2 * ind] > val) return ans = ind; return ans = (2 * ind); } // case 1: if (val < arr[2 * ind] && val < arr[2 * ind + 1]) { return ans = ind; } // case 2: else if (arr[2 * ind] < min(val, arr[2 * ind + 1])) { return ans = f(2 * ind, val); } // case 3: else { int a = min(val, arr[2 * ind]); int b = max(val, arr[2 * ind]); int c = arr[2 * ind + 1]; int t1 = f(2 * ind, a), t2 = f(2 * ind + 1, a); if (t1 < t2) { if (a == val) return ans = t1; return ans = f(2 * ind + 1, val); } else { if (a == val) return ans = t2; return ans = f(2 * ind, val); } } } int solve() { cin >> n; for (int i = 1; i <= n; i++) { cin >> arr[i]; } arr[n + 1] = inf; for (int i = 1; i <= n; i++) { if (i * 2 <= n) { // case 1: if (arr[i] < arr[2 * i] && arr[i] < arr[2 * i + 1]) continue; // case 2: else if (arr[2 * i] < min(arr[i], arr[2 * i + 1])) { swap(arr[i], arr[2 * i]); } // case 3: else { int a = min(arr[i], arr[2 * i]); int b = max(arr[i], arr[2 * i]); int c = arr[2 * i + 1]; arr[i] = c; int t1 = f(2 * i, a), t2 = f(2 * i + 1, a); if (t1 < t2) { arr[2 * i] = a; arr[2 * i + 1] = b; } else { arr[2 * i] = b; arr[2 * i + 1] = a; } } } } for (int i = 1; i <= n; i++) { cout << arr[i] << " "; } cout << endl; return 0; } int32_t main(){ _ int t; // cin >> t; t = 1; while (t--) solve(); }

Compilation message (stderr)

swap.cpp: In function 'int f(int, int)':
swap.cpp:87:13: warning: unused variable 'b' [-Wunused-variable]
         int b = max(val, arr[2 * ind]);
             ^
swap.cpp:88:13: warning: unused variable 'c' [-Wunused-variable]
         int c = arr[2 * ind + 1];
             ^
#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...