oj.uz

Submission #1048654

# Submission time Handle Problem Language Result Execution time Memory
1048654 2024-08-08T08:57:03 Z TAhmed33 Swap (BOI16_swap) C++
48 / 100
 11 ms 1324 KB 
#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];
map <pair <int, int>, vector <int>> memo;
vector <int> ans (int pos, int x) {
	if (memo.count({pos, x})) {
		return memo[{pos, 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 memo[{pos, x}] = 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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 6 ms 1116 KB Output is correct
12 Correct 11 ms 1324 KB Output is correct
13 Correct 6 ms 1112 KB Output is correct
14 Correct 6 ms 1116 KB Output is correct
15 Correct 7 ms 1116 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 6 ms 1116 KB Output is correct
12 Correct 11 ms 1324 KB Output is correct
13 Correct 6 ms 1112 KB Output is correct
14 Correct 6 ms 1116 KB Output is correct
15 Correct 7 ms 1116 KB Output is correct
16 Runtime error 0 ms 604 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 6 ms 1116 KB Output is correct
12 Correct 11 ms 1324 KB Output is correct
13 Correct 6 ms 1112 KB Output is correct
14 Correct 6 ms 1116 KB Output is correct
15 Correct 7 ms 1116 KB Output is correct
16 Runtime error 0 ms 604 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -