| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 933202 |
2024-02-25T09:02:24 Z |
LucaIlie |
Swap (BOI16_swap) |
C++17 |
|
172 ms |
49752 KB |
#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 time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12888 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12888 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 6 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12904 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 9 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 10 |
Correct |
3 ms |
12892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12888 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 6 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12904 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 9 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 10 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 11 |
Correct |
4 ms |
12888 KB |
Output is correct |
| 12 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 13 |
Correct |
4 ms |
12892 KB |
Output is correct |
| 14 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 15 |
Correct |
3 ms |
12892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12888 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 6 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12904 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 9 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 10 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 11 |
Correct |
4 ms |
12888 KB |
Output is correct |
| 12 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 13 |
Correct |
4 ms |
12892 KB |
Output is correct |
| 14 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 15 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 16 |
Correct |
27 ms |
16984 KB |
Output is correct |
| 17 |
Correct |
25 ms |
16980 KB |
Output is correct |
| 18 |
Correct |
26 ms |
17016 KB |
Output is correct |
| 19 |
Correct |
37 ms |
21588 KB |
Output is correct |
| 20 |
Correct |
38 ms |
21596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
12888 KB |
Output is correct |
| 2 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 5 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 6 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 7 |
Correct |
3 ms |
12904 KB |
Output is correct |
| 8 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 9 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 10 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 11 |
Correct |
4 ms |
12888 KB |
Output is correct |
| 12 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 13 |
Correct |
4 ms |
12892 KB |
Output is correct |
| 14 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 15 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 16 |
Correct |
27 ms |
16984 KB |
Output is correct |
| 17 |
Correct |
25 ms |
16980 KB |
Output is correct |
| 18 |
Correct |
26 ms |
17016 KB |
Output is correct |
| 19 |
Correct |
37 ms |
21588 KB |
Output is correct |
| 20 |
Correct |
38 ms |
21596 KB |
Output is correct |
| 21 |
Correct |
102 ms |
30676 KB |
Output is correct |
| 22 |
Correct |
107 ms |
31444 KB |
Output is correct |
| 23 |
Correct |
102 ms |
31332 KB |
Output is correct |
| 24 |
Correct |
172 ms |
49752 KB |
Output is correct |
| 25 |
Correct |
169 ms |
49744 KB |
Output is correct |
