oj.uz

Submission #1048850

# Submission time Handle Problem Language Result Execution time Memory
1048850 2024-08-08T09:52:48 Z TAhmed33 Swap (BOI16_swap) C++
68 / 100
 500 ms 112840 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];
vector <pair <int, vector <int>>> dp[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 solve () {
	cin >> n; nn = n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	while (__builtin_popcount(n + 1) != 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) {
				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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 5208 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 5208 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 1 ms 5156 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5164 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 5208 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 1 ms 5156 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5164 KB Output is correct
11 Correct 5 ms 6236 KB Output is correct
12 Correct 5 ms 6420 KB Output is correct
13 Correct 5 ms 6236 KB Output is correct
14 Correct 5 ms 6444 KB Output is correct
15 Correct 5 ms 6244 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 5208 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 1 ms 5156 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5164 KB Output is correct
11 Correct 5 ms 6236 KB Output is correct
12 Correct 5 ms 6420 KB Output is correct
13 Correct 5 ms 6236 KB Output is correct
14 Correct 5 ms 6444 KB Output is correct
15 Correct 5 ms 6244 KB Output is correct
16 Correct 432 ms 112276 KB Output is correct
17 Correct 438 ms 112308 KB Output is correct
18 Correct 456 ms 112020 KB Output is correct
19 Correct 498 ms 112544 KB Output is correct
20 Correct 500 ms 112840 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 5208 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 1 ms 5156 KB Output is correct
9 Correct 1 ms 5212 KB Output is correct
10 Correct 1 ms 5164 KB Output is correct
11 Correct 5 ms 6236 KB Output is correct
12 Correct 5 ms 6420 KB Output is correct
13 Correct 5 ms 6236 KB Output is correct
14 Correct 5 ms 6444 KB Output is correct
15 Correct 5 ms 6244 KB Output is correct
16 Correct 432 ms 112276 KB Output is correct
17 Correct 438 ms 112308 KB Output is correct
18 Correct 456 ms 112020 KB Output is correct
19 Correct 498 ms 112544 KB Output is correct
20 Correct 500 ms 112840 KB Output is correct
21 Runtime error 14 ms 12380 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -