Submission #114388

#	Time	Username	Problem	Language	Result	Execution time	Memory
114388		atoiz	Swap (BOI16_swap)	C++14	100 / 100	53 ms	4476 KiB

swap

/*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 (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: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;
                                    ^~~~

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