| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 27107 |
2017-07-09T09:26:48 Z |
윤교준(#1121) |
Swap (BOI16_swap) |
C++11 |
|
0 ms |
3580 KB |
#include <bits/stdc++.h>
#define pb push_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[(sz(V)-2)])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define rb(x) ((x)&(-(x)))
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define MAXN (200005)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int A[MAXN], B[MAXN];
int N;
int main() {
scanf("%d", &N);
for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
if(N <= 2) {
sort(A+1, A+N+1);
for(int i = 1; i <= N; i++) printf("%d ", A[i]);
return 0;
}
B[1] = (int)(min_element(A+1, A+4) - A);
swap(A[1], A[B[1]]);
for(int i = 2; i <= N; i++) {
if(i&1) {
int ret = A[i], idx = i;
if(i*2 <= N && A[i*2] < ret) tie(ret, idx) = (pii){A[i*2], i*2};
if(i*2+1 <= N && A[i*2+1] < ret) tie(ret, idx) = (pii){A[i*2+1], i*2+1};
B[i] = idx; swap(A[i], A[B[i]]);
} else {
int ret = A[i], idx = i;
if(i*2 <= N && A[i*2] < ret) tie(ret, idx) = (pii){A[i*2], i*2};
if(i*2+1 <= N && A[i*2+1] < ret) tie(ret, idx) = (pii){A[i*2+1], i*2+1};
if(i+1 <= N && A[i+1] < ret && B[i/2] == i+1) tie(ret, idx) = (pii){A[i+1], i+1};
B[i] = idx; swap(A[i], A[B[i]]);
}
}
for(int i = 1; i <= N; i++) printf("%d ", A[i]);
puts("");
return 0;
}
Compilation message
swap.cpp: In function 'int main()':
swap.cpp:26:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
swap.cpp:27:48: 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]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
3580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
3580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
3580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
3580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
3580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
