| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 258586 |
2020-08-06T07:43:29 Z |
송준혁(#5060) |
Swap (BOI16_swap) |
C++17 |
|
3 ms |
4224 KB |
#include <bits/stdc++.h>
#define pb push_back
#define lb lower_bound
#define fi first
#define se second
#define mup(a,x) a=min(a,x)
#define Mup(a,x) a=max(a,x)
#define INF 1234567890
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N;
int A[1010], D[1010][1010];
int f(int u, int x){
if (D[u][x]) return D[u][x];
if (2*u > N) return D[u][x] = u;
if (2*u == N){
if (A[2*u] < x) return D[u][x] = f(2*u, x);
return D[u][x] = u;
}
if (A[2*u] > x && A[2*u+1] > x) return D[u][x] = u;
if (A[2*u] < x && A[2*u] < A[2*u+1]) return D[u][x] = f(2*u, x);
if (A[2*u] < x){
if (f(2*u, A[2*u]) < f(2*u+1, A[2*u])) return D[u][x] = f(2*u+1, x);
return D[u][x] = f(2*u, x);
}
if (f(2*u, x) < f(2*u+1, x)) return D[u][x] = f(2*u, x);
return D[u][x] = f(2*u+1, x);
}
void g(int u){
if (2*u > N) return;
if (2*u == N){
if (A[2*u] < A[u]) swap(A[u], A[2*u]);
return;
}
if (A[2*u] < A[u] && A[2*u] < A[2*u+1]) swap(A[u], A[2*u]);
else if (A[u] > A[2*u+1] && A[2*u] > A[2*u+1]){
if (A[2*u] < A[u]){
if (f(2*u, A[2*u]) < f(2*u+1, A[2*u])) swap(A[u], A[2*u+1]);
else swap(A[2*u], A[2*u+1]), swap(A[u], A[2*u]);
}
else{
if (f(2*u, A[u]) < f(2*u+1, A[u])) swap(A[2*u], A[2*u+1]), swap(A[u], A[2*u]);
else swap(A[u], A[2*u+1]);
}
}
g(2*u), g(2*u+1);
}
int main(){
scanf("%d", &N);
for (int i=1; i<=N; i++) scanf("%d", &A[i]);
g(1);
for (int i=1; i<=N; i++) printf("%d ", A[i]);
printf("\n");
return 0;
}
Compilation message
swap.cpp: In function 'int main()':
swap.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
swap.cpp:55:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i=1; i<=N; i++) scanf("%d", &A[i]);
~~~~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
512 KB |
Output is correct |
| 10 |
Correct |
0 ms |
512 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
512 KB |
Output is correct |
| 10 |
Correct |
0 ms |
512 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2432 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2432 KB |
Output is correct |
| 13 |
Correct |
2 ms |
2432 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 15 |
Correct |
3 ms |
4224 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
512 KB |
Output is correct |
| 10 |
Correct |
0 ms |
512 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2432 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2432 KB |
Output is correct |
| 13 |
Correct |
2 ms |
2432 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 15 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 16 |
Runtime error |
1 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
384 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| 7 |
Correct |
0 ms |
384 KB |
Output is correct |
| 8 |
Correct |
0 ms |
384 KB |
Output is correct |
| 9 |
Correct |
1 ms |
512 KB |
Output is correct |
| 10 |
Correct |
0 ms |
512 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2432 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2432 KB |
Output is correct |
| 13 |
Correct |
2 ms |
2432 KB |
Output is correct |
| 14 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 15 |
Correct |
3 ms |
4224 KB |
Output is correct |
| 16 |
Runtime error |
1 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Halted |
0 ms |
0 KB |
- |
