Submission #1048747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048747		TAhmed33	Swap (BOI16_swap)	C++98	68 / 100	568 ms	122192 KiB

swap

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 25;
vector <int> merge (int x, vector <int> a, vector <int> b) {
	vector <int> ret = {x};
	reverse(a.begin(), a.end()); reverse(b.begin(), b.end());
	for (int i = 0; ; i++) {
		if (a.empty() || b.empty()) break;
		for (int k = 0; k < (1 << i); k++) {
			ret.push_back(a.back()); a.pop_back();
		}
		for (int k = 0; k < (1 << i); k++) {
			ret.push_back(b.back()); b.pop_back();
		}
	}
	return ret;
}
int nn, n, a[MAXN];
map <int, vector <int>> dp[MAXN];
void solve () {
	cin >> n; nn = n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	while (__builtin_popcount(n) != 1) {
		a[++n] = n;
	}
	for (int i = n; i >= 1; i--) {
		vector <int> x;
		int j = i;
		while (j >= 1) {
			x.push_back(a[j]);
			if (2 * j <= n) x.push_back(a[2 * j]);
			if (2 * j + 1 <= n) x.push_back(a[2 * j + 1]);
			j /= 2;
		}
		sort(x.begin(), x.end());
		x.resize(unique(x.begin(), x.end()) - x.begin());
		for (auto j : x) {
			if (2 * i > n) {
				dp[i][j] = {j};
				continue;
			}
			if (2 * i + 1 > n) {
				if (a[2 * i] > j) {
					dp[i][j] = {j, a[2 * i]};
				} else {
					dp[i][j] = {a[2 * i], j};
				}
				continue;
			}
			if (j < a[2 * i] && j < a[2 * i + 1]) {
				dp[i][j] = merge(j, dp[2 * i][a[2 * i]], dp[2 * i + 1][a[2 * i + 1]]);
				continue;
			}
			if (a[2 * i] < j && a[2 * i] < a[2 * i + 1]) {
				dp[i][j] = merge(a[2 * i], dp[2 * i][j], dp[2 * i + 1][a[2 * i + 1]]);
				continue;
			}
			dp[i][j] = min({
				merge(a[2 * i + 1], dp[2 * i][a[2 * i]], dp[2 * i + 1][j]),
				merge(a[2 * i + 1], dp[2 * i][j], dp[2 * i + 1][a[2 * i]])
			});
		}
		if (2 * i <= n) dp[2 * i].clear();
		if (2 * i + 1 <= n) dp[2 * i + 1].clear();
	}
	auto g = dp[1][a[1]];
	for (int j = 0; j < nn; j++) {
		cout << g[j] << " ";
	}
	cout << '\n';
}		
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int tc = 1; //cin >> tc;
	while (tc--) solve();
}

Compilation message (stderr)

swap.cpp: In function 'void solve()':
swap.cpp:26:5: warning: operation on 'n' may be undefined [-Wsequence-point]
   26 |   a[++n] = n;
      |     ^~~
swap.cpp:26:5: warning: operation on 'n' may be undefined [-Wsequence-point]

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