/*input
40
25 39 38 37 36 35 34 33 28 31 30 29 32 27 26 19 4 23 22 12 20 40 18 17 16 15 14 11 21 13 10 9 8 7 6 5 24 3 2 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];
int L[MAXN], R[MAXN], par[MAXN], curId[MAXN], last = 0;
bool dead[MAXN];
void kill(int id, int i)
{
while (id && !dead[id] && (L[id] == i || R[id] == i)) {
dead[id] = 1;
id = par[id];
}
}
int getMin(int id)
{
int ans = MAXN;
while (id && !dead[id]) {
ans = min(ans, min(a[L[id]], a[R[id]]));
id = par[id];
}
return ans;
}
void change(int id, int from, int to)
{
while (id && !dead[id]) {
if (L[id] == from) L[id] = to;
else if (R[id] == from) R[id] = to;
else return;
id = par[id];
}
}
void retrieve(int id, int i, int curMin)
{
cerr << "retrieve " << id << ' ' << i << ' ' << curMin << endl;
dead[id] = 1;
int p = par[id];
if (a[L[id]] != curMin && a[R[id]] != curMin) {
assert(p && !dead[p]);
if (L[p] != L[id] && R[p] != L[id]) swap(L[id], R[id]);
retrieve(p, L[id], curMin);
}
if (a[L[id]] != curMin) swap(L[id], R[id]);
if (p && !dead[p]) kill(p, L[id]);
if (R[id] == i) {
// if (p && !dead[p]) change(p, R[id], L[id]);
swap(a[L[id]], a[R[id]]);
}
assert(a[i] == curMin);
}
void refresh(int i)
{
while (curId[i] && dead[curId[i]]) curId[i] = par[curId[i]];
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n; FOR(i, 1, n) cin >> a[i];
FOR(i, 1, n) {
// cerr << "S " << i-1 << ": "; FOR(i, 1, n) cerr << a[i] << ' '; cerr << endl;
// if (i == 4) cout << curId[i] << endl;
refresh(i);
if (curId[i] && !dead[curId[i]]) {
int curMin = getMin(curId[i]);
// cout << "curMin " << i << ": " << curMin << endl;
if (i * 2 > n) retrieve(curId[i], i, curMin);
else if (i * 2 + 1 > n) {
if (curMin < a[i * 2]) retrieve(curId[i], i, curMin);
else {
change(curId[i], i, i * 2);
swap(a[i], a[i * 2]);
curId[i * 2] = curId[i];
}
} else if (curMin < a[i * 2] && curMin < a[i * 2 + 1]) retrieve(curId[i], i, curMin);
else if (a[i * 2] < a[i * 2 + 1]) {
change(curId[i], i, i * 2);
swap(a[i], a[i * 2]);
curId[i * 2] = curId[i];
} else {
change(curId[i], i, i * 2 + 1);
swap(a[i], a[i * 2 + 1]);
int id = curId[i * 2] = curId[i * 2 + 1] = ++last;
L[id] = i * 2, R[id] = i * 2 + 1; par[id] = curId[i];
}
} else {
if (i * 2 > n) continue;
else if (i * 2 + 1 > n) {
if (a[i] > a[i * 2]) swap(a[i], a[i * 2]);
} else if (a[i] < a[i * 2] && a[i] < a[i * 2 + 1]) continue;
else if (a[i * 2] < a[i * 2 + 1]) swap(a[i], a[i * 2]);
else {
swap(a[i], a[i * 2 + 1]);
int id = curId[i * 2] = curId[i * 2 + 1] = ++last;
L[id] = i * 2, R[id] = i * 2 + 1; par[id] = 0;
}
}
// if (i == 28) {
// cout << curId[29] << ": " << getMin(curId[29]) << endl;
// FOR(j, 1, n) cout << a[j] << ' '; cout << endl;
// FOR(id, 1, last) {
// // if (!dead[id])
// cout << id << ": " << L[id] << ' ' << R[id] << " _ " << par[id] << ' ' << (dead[id] ? "dead" : "alive") << endl;
// }
// }
}
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:151:2: note: in expansion of macro 'FOR'
FOR(i, 1, n) cout << a[i] << ' '; cout << endl;
^~~
swap.cpp:151: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 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
