oj.uz

답안 #1048644

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1048644 2024-08-08T08:55:15 Z TAhmed33 Swap (BOI16_swap) C++
21 / 100
 1000 ms 456 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];
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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 456 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 456 KB Output is correct
11 Execution timed out 1066 ms 348 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 456 KB Output is correct
11 Execution timed out 1066 ms 348 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 456 KB Output is correct
11 Execution timed out 1066 ms 348 KB Time limit exceeded
12 Halted 0 ms 0 KB -