/*input
5
3 4 2 5 1
*/
#include <iostream>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <cassert>
#include <algorithm>
#include <cstdlib>
#include <numeric>
#include <climits>
#include <fstream>
using namespace std;
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define FORA(i, a) for (auto &i : a)
#define SZ(a) ((int) a.size())
#define ALL(a) begin(a), end(a)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define fi first
#define se second
const int MAXN = 200007;
int N, A[MAXN << 1], dir[MAXN << 1];
int getMin(int u, int t)
{
int ans = MAXN;
if (t >= 0) {
if (dir[u] == 0) ans = A[u];
else {
int x = getMin(u >> 1, u & 1);
if (dir[u] == 1) ans = x;
else ans = min(x, A[u]);
}
}
if (t >= 1) {
if (dir[u * 2] == 0);
else if (dir[u * 2] == 1) ans = A[u * 2];
else ans = min(ans, A[u * 2]);
}
if (t >= 2) {
// probably redundant
assert(0);
}
return ans;
}
void retrieve(int u, int t, int curMin)
{
// cout << "RE " << u << ' ' << t << ' ' << curMin << endl;
if (A[u] == curMin) {
if (t >= 0) {
assert(dir[u] != 1);
dir[u] = 0;
}
if (t >= 1) {
assert(dir[u * 2] != 1);
dir[u * 2] = 0;
}
} else if (A[u * 2] == curMin) {
assert(t >= 1);
assert(dir[u * 2] != 0);
dir[u * 2] = 1;
} else if (A[u * 2 + 1] == curMin) {
assert(t >= 2); // or in other words, assert(0);
} else {
assert(dir[u] != 0);
retrieve(u >> 1, u & 1, curMin);
if (t >= 0) {
assert(dir[u] != 0);
dir[u] = 1;
}
if (t >= 1) {
assert(dir[u * 2] != 1);
dir[u * 2] = 0;
}
}
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N;
FOR(i, 1, N) cin >> A[i];
dir[1] = 0; FOR(i, 2, N) dir[i] = -1;
FOR(i, 1, N) {
int curMin = getMin(i, 0);
if (i * 2 > N) retrieve(i, 0, curMin);
else if (i * 2 + 1 > N) {
if (curMin > A[i * 2]) dir[i * 2] = 1;
else {
dir[i * 2] = 0;
retrieve(i, 0, curMin);
}
} else if (curMin < A[i * 2] && curMin < A[i * 2 + 1]) {
dir[i * 2] = dir[i * 2 + 1] = 0;
retrieve(i, 0, curMin);
} else if (A[i * 2] < A[i * 2 + 1]) {
dir[i * 2] = 1; dir[i * 2 + 1] = 0;
} else dir[i * 2 + 1] = 1;
// cout << i << ": ";
// FOR(i, 1, N) cout << dir[i] << ' ';
// cout << endl;
}
FOR(i, 2, N) if (dir[i] == 1) swap(A[i], A[i >> 1]);
FOR(i, 1, N) cout << A[i] << ' '; cout << endl;
return 0;
}
Compilation message
swap.cpp: In function 'int main()':
swap.cpp:21:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
^
swap.cpp:124:2: note: in expansion of macro 'FOR'
FOR(i, 1, N) cout << A[i] << ' '; cout << endl;
^~~
swap.cpp:124:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
FOR(i, 1, N) cout << A[i] << ' '; cout << endl;
^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 ms |
384 KB |
Output is correct |
| 15 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 ms |
384 KB |
Output is correct |
| 15 |
Correct |
2 ms |
384 KB |
Output is correct |
| 16 |
Correct |
12 ms |
1380 KB |
Output is correct |
| 17 |
Correct |
12 ms |
1280 KB |
Output is correct |
| 18 |
Correct |
13 ms |
1280 KB |
Output is correct |
| 19 |
Correct |
14 ms |
1408 KB |
Output is correct |
| 20 |
Correct |
13 ms |
1408 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
384 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
384 KB |
Output is correct |
| 13 |
Correct |
2 ms |
384 KB |
Output is correct |
| 14 |
Correct |
2 ms |
384 KB |
Output is correct |
| 15 |
Correct |
2 ms |
384 KB |
Output is correct |
| 16 |
Correct |
12 ms |
1380 KB |
Output is correct |
| 17 |
Correct |
12 ms |
1280 KB |
Output is correct |
| 18 |
Correct |
13 ms |
1280 KB |
Output is correct |
| 19 |
Correct |
14 ms |
1408 KB |
Output is correct |
| 20 |
Correct |
13 ms |
1408 KB |
Output is correct |
| 21 |
Correct |
43 ms |
4472 KB |
Output is correct |
| 22 |
Correct |
43 ms |
4472 KB |
Output is correct |
| 23 |
Correct |
42 ms |
4472 KB |
Output is correct |
| 24 |
Correct |
53 ms |
4476 KB |
Output is correct |
| 25 |
Correct |
53 ms |
4472 KB |
Output is correct |
