Submission #933202

#TimeUsernameProblemLanguageResultExecution timeMemory
933202LucaIlieSwap (BOI16_swap)C++17
100 / 100
172 ms49752 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 2e5; int v[2 * MAX_N + 2]; unordered_map<int, int> dp[MAX_N + 1]; int DP( int i, int x ) { if ( dp[i][x] != 0 ) return dp[i][x]; if ( x < v[2 * i] && x < v[2 * i + 1] ) dp[i][x] = i; else if ( v[2 * i] < v[2 * i + 1] ) dp[i][x] = DP( 2 * i, x ); else { if ( x < v[2 * i] ) { DP( 2 * i, x ); DP( 2 * i + 1, x ); if ( dp[2 * i][x] < dp[2 * i + 1][x] ) dp[i][x] = DP( 2 * i, x ); else dp[i][x] = DP( 2 * i + 1, x ); } else { DP( 2 * i, v[2 * i] ); DP( 2 * i + 1, v[2 * i] ); if ( dp[2 * i][v[2 * i]] < dp[2 * i + 1][v[2 * i]] ) dp[i][x] = DP( 2 * i + 1, x ); else dp[i][x] = DP( 2 * i, x ); } } return dp[i][x]; } int main() { int n; cin >> n; for ( int i = 1; i <= n; i++ ) cin >> v[i]; for ( int i = n + 1; i <= 2 * n + 1; i++ ) v[i] = n + 1; for ( int i = 1; 2 * i + 1 <= n; i++ ) { if ( v[2 * i] < v[i] && v[2 * i] < v[2 * i + 1] ) swap( v[i], v[2 * i] ); else if ( v[2 * i + 1] < v[i] && v[2 * i + 1] < v[2 * i] ) { swap( v[i], v[2 * i + 1] ); if ( v[2 * i] < v[2 * i + 1] ) { if ( DP( 2 * i, v[2 * i] ) > DP( 2 * i + 1, v[2 * i] ) ) swap( v[2 * i], v[2 * i + 1] ); } else { if ( DP( 2 * i, v[2 * i + 1] ) < DP( 2 * i + 1, v[2 * i + 1] ) ) swap( v[2 * i], v[2 * i + 1] ); } } } if ( v[n / 2] > v[n] ) swap( v[n / 2], v[n] ); for ( int i = 1; i <= n; i++ ) cout << v[i] << " "; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...