Submission #1048861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048861		TAhmed33	Swap (BOI16_swap)	C++98	68 / 100	306 ms	69860 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];
vector <pair <int, vector <int>>> dp[MAXN];
vector <pair <int, int>> bad[MAXN];
void insert (int i, int j, vector <int> x) {
	dp[i].push_back({j, x});
}
vector <int> get (int i, int j) {
	pair <int, vector <int>> z = {j, {0}};
	auto x = lower_bound(dp[i].begin(), dp[i].end(), z);
	return (*x).second;
}
void insert2 (int i, int j) {
	pair <int, int> g = {j, 0};
	auto h = lower_bound(bad[i].begin(), bad[i].end(), g) - bad[i].begin();
	bad[i][h].second = 1;
}
int get2 (int i, int j) {
	pair <int, int> g = {j, 0};
	auto h = lower_bound(bad[i].begin(), bad[i].end(), g);
	return (*h).second;
}
void solve () {
	cin >> n; nn = n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	while (__builtin_popcount(n + 1) != 1) {
		a[++n] = n;
	}
	bad[1].push_back({a[1], 0});
	for (int i = 1; i <= n; 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) {
			bad[i].push_back({j, 0});
		}
	}
	insert2(1, a[1]);
	for (int i = 1; i <= n; i++) {
		for (auto [j, k] : bad[i]) {
			if (!k) {
				continue;
			}
			if (2 * i > n) {
				continue;
			}
			if (j < a[2 * i] && j < a[2 * i + 1]) {
				insert2(2 * i, a[2 * i]);
				insert2(2 * i + 1, a[2 * i + 1]);
				continue;
			}
			if (a[2 * i] < j && a[2 * i] < a[2 * i + 1]) {
				insert2(2 * i, j); insert2(2 * i + 1, a[2 * i + 1]);
				continue;
			}
			insert2(2 * i, a[2 * i]); insert2(2 * i + 1, j);
			insert2(2 * i, j); insert2(2 * i + 1, a[2 * i]);
		}
	}
	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 (!get2(i, j)) {
				continue;
			}
			if (2 * i > n) {
				insert(i, j, {j});
				continue;
			}
			if (j < a[2 * i] && j < a[2 * i + 1]) {
				insert(i, j, merge(j, get(2 * i, a[2 * i]), get(2 * i + 1, a[2 * i + 1])));
				continue;
			}
			if (a[2 * i] < j && a[2 * i] < a[2 * i + 1]) {
				insert(i, j, merge(a[2 * i], get(2 * i, j), get(2 * i + 1, a[2 * i + 1])));
				continue;
			}
			insert(i, j, min({
				merge(a[2 * i + 1], get(2 * i, a[2 * i]), get(2 * i + 1, j)),
				merge(a[2 * i + 1], get(2 * i, j), get(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 = get(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:45:5: warning: operation on 'n' may be undefined [-Wsequence-point]
   45 |   a[++n] = n;
      |     ^~~
swap.cpp:45:5: warning: operation on 'n' may be undefined [-Wsequence-point]
swap.cpp:65:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |   for (auto [j, k] : bad[i]) {
      |             ^

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