제출 #114387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114387		atoiz	Swap (BOI16_swap)	C++14	0 / 100	2 ms	384 KiB

swap

/*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;
}

컴파일 시 표준 에러 (stderr) 메시지

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;
                                    ^~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 11
• Subtask 3: 0 / 27
• Subtask 4: 0 / 20
• Subtask 5: 0 / 32