Submission #101296

#	Time	Username	Problem	Language	Result	Execution time	Memory
101296		aome	Swap (BOI16_swap)	C++17	100 / 100	64 ms	4896 KiB

swap

#include <bits/stdc++.h>

using namespace std;

const int N = 200005;

int n, p[N];
int res[N];
bool flag[N];
bool visit[N];

void brute() {
	vector<int> opt;
	for (int i = 1; i <= n; ++i) opt.push_back(p[i]);
	for (int i = 0; i < (1 << (n - 1)); ++i) {
		vector<int> vec;
		for (int j = 1; j <= n; ++j) vec.push_back(p[j]);
		for (int j = 2; j <= n; ++j) {
			if (i >> (j - 2) & 1) {
				swap(vec[j - 1], vec[j / 2 - 1]);
			}
		}
		if (opt > vec) opt = vec;
	}
	for (auto i : opt) cout << i << ' '; cout << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> p[i];
	// brute();
	flag[1] = 1;
	for (int i = 1; i <= n; ++i) {
		if (flag[i]) {
			int mn = 1e9;
			if (i * 2 <= n) mn = min(mn, p[i * 2]);
			if (i * 2 + 1 <= n) mn = min(mn, p[i * 2 + 1]);
			if (mn > p[i]) {
				res[i] = p[i];
				if (i * 2 <= n) flag[i * 2] = 1;
				if (i * 2 + 1 <= n) flag[i * 2 + 1] = 1;
			} 
			else {
				if (i * 2 <= n && mn == p[i * 2]) {
					swap(p[i], p[i * 2]), res[i] = p[i];
					flag[i * 2] = 1;
					if (i * 2 + 1 <= n) flag[i * 2 + 1] = 1;
				}
				else {
					swap(p[i], p[i * 2 + 1]), res[i] = p[i];
				}
			}
		}
		else {
			int mn = 1e9;
			int cur = i;
			while (1) {
				if (visit[cur]) break;
				cur /= 2;
				mn = min(mn, p[cur * 2]);
				if (flag[cur]) {
					if (cur * 2 + 1 <= n) mn = min(mn, p[cur * 2 + 1]); 
					break;
				}			
			}
			int mn2 = 1e9;
			if (i * 2 <= n) mn2 = min(mn2, p[i * 2]);
			if (i * 2 + 1 <= n) mn2 = min(mn2, p[i * 2 + 1]);
			if (mn > mn2) {
				if (i * 2 <= n && mn2 == p[i * 2]) {
					res[i] = p[i * 2], p[i * 2] = 1e9;
					if (i * 2 + 1 <= n) flag[i * 2 + 1] = 1;
				}
				else {
					res[i] = p[i * 2 + 1];
				}
			}
			else {
				res[i] = mn;
				if (i * 2 <= n) flag[i * 2] = 1;
				if (i * 2 + 1 <= n) flag[i * 2 + 1] = 1;
				cur = i;
				while (1) {
					visit[cur] = 1, cur /= 2;
					if (mn == p[cur * 2]) {
						p[cur * 2] = 1e9; break;
					}
					if (flag[cur]) {
						if (cur * 2 + 1 <= n) {
							if (mn == p[cur * 2 + 1]) {
								p[cur * 2 + 1] = 1e9;
							}
						}
						break;
					}
				}
			}
		}
	}
	for (int i = 1; i <= n; ++i) cout << res[i] << ' ';
}

Compilation message (stderr)

swap.cpp: In function 'void brute()':
swap.cpp:25:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (auto i : opt) cout << i << ' '; cout << '\n';
  ^~~
swap.cpp:25:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (auto i : opt) cout << i << ' '; cout << '\n';
                                       ^~~~

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