Submission #1048644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048644		TAhmed33	Swap (BOI16_swap)	C++98	21 / 100	1066 ms	456 KiB

swap

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 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];
vector <int> ans (int pos, int x) {
	if (2 * pos > n) {
		return {x};
	}
	if (2 * pos + 1 > n) {
		if (a[2 * pos] > x) {
			return {x, a[2 * pos]};
		} else {
			return {a[2 * pos], x};
		}
	}
	return min({
		merge(x, ans(2 * pos, a[2 * pos]), ans(2 * pos + 1, a[2 * pos + 1])),
		merge(a[2 * pos], ans(2 * pos, x), ans(2 * pos + 1, a[2 * pos + 1])),
		merge(a[2 * pos + 1], ans(2 * pos, a[2 * pos]), ans(2 * pos + 1, x)),
		merge(a[2 * pos + 1], ans(2 * pos, x), ans(2 * pos + 1, a[2 * pos]))
	});
}
void solve () {
	cin >> n; nn = n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	while (__builtin_popcount(n) != 1) {
		a[++n] = n;
	}
	auto g = ans(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:43:5: warning: operation on 'n' may be undefined [-Wsequence-point]
   43 |   a[++n] = n;
      |     ^~~
swap.cpp:43:5: warning: operation on 'n' may be undefined [-Wsequence-point]

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