#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000;
int v[2 * MAX_N + 2], dp[MAX_N + 1][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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |