oj.uz

Submission #1048747

# Submission time Handle Problem Language Result Execution time Memory
1048747 2024-08-08T09:21:52 Z TAhmed33 Swap (BOI16_swap) C++
68 / 100
 568 ms 122192 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 1 ms 9820 KB Output is correct
3 Correct 1 ms 9820 KB Output is correct
4 Correct 1 ms 9820 KB Output is correct
5 Correct 1 ms 9820 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 1 ms 9820 KB Output is correct
3 Correct 1 ms 9820 KB Output is correct
4 Correct 1 ms 9820 KB Output is correct
5 Correct 1 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 1 ms 9820 KB Output is correct
8 Correct 1 ms 9896 KB Output is correct
9 Correct 2 ms 9816 KB Output is correct
10 Correct 2 ms 9816 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 1 ms 9820 KB Output is correct
3 Correct 1 ms 9820 KB Output is correct
4 Correct 1 ms 9820 KB Output is correct
5 Correct 1 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 1 ms 9820 KB Output is correct
8 Correct 1 ms 9896 KB Output is correct
9 Correct 2 ms 9816 KB Output is correct
10 Correct 2 ms 9816 KB Output is correct
11 Correct 5 ms 10840 KB Output is correct
12 Correct 5 ms 10844 KB Output is correct
13 Correct 7 ms 10844 KB Output is correct
14 Correct 7 ms 10888 KB Output is correct
15 Correct 5 ms 10840 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 1 ms 9820 KB Output is correct
3 Correct 1 ms 9820 KB Output is correct
4 Correct 1 ms 9820 KB Output is correct
5 Correct 1 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 1 ms 9820 KB Output is correct
8 Correct 1 ms 9896 KB Output is correct
9 Correct 2 ms 9816 KB Output is correct
10 Correct 2 ms 9816 KB Output is correct
11 Correct 5 ms 10840 KB Output is correct
12 Correct 5 ms 10844 KB Output is correct
13 Correct 7 ms 10844 KB Output is correct
14 Correct 7 ms 10888 KB Output is correct
15 Correct 5 ms 10840 KB Output is correct
16 Correct 524 ms 122192 KB Output is correct
17 Correct 551 ms 121840 KB Output is correct
18 Correct 537 ms 121828 KB Output is correct
19 Correct 568 ms 121964 KB Output is correct
20 Correct 519 ms 121908 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9816 KB Output is correct
2 Correct 1 ms 9820 KB Output is correct
3 Correct 1 ms 9820 KB Output is correct
4 Correct 1 ms 9820 KB Output is correct
5 Correct 1 ms 9820 KB Output is correct
6 Correct 2 ms 9816 KB Output is correct
7 Correct 1 ms 9820 KB Output is correct
8 Correct 1 ms 9896 KB Output is correct
9 Correct 2 ms 9816 KB Output is correct
10 Correct 2 ms 9816 KB Output is correct
11 Correct 5 ms 10840 KB Output is correct
12 Correct 5 ms 10844 KB Output is correct
13 Correct 7 ms 10844 KB Output is correct
14 Correct 7 ms 10888 KB Output is correct
15 Correct 5 ms 10840 KB Output is correct
16 Correct 524 ms 122192 KB Output is correct
17 Correct 551 ms 121840 KB Output is correct
18 Correct 537 ms 121828 KB Output is correct
19 Correct 568 ms 121964 KB Output is correct
20 Correct 519 ms 121908 KB Output is correct
21 Runtime error 23 ms 22364 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -