Submission #391072

#	Time	Username	Problem	Language	Result	Execution time	Memory
391072		kostia244	Swap (BOI16_swap)	C++17	68 / 100	1084 ms	8652 KiB

swap

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int maxn = 1<<18;
const ll inf = 1ll<<60;
int n, a[maxn], B[maxn], C[maxn];
using stri = basic_string<int>;
stri mer(stri a, stri b) {
	stri res;
	res.reserve(a.size()+b.size());
	for(int i = 0, j = 0, len = 1; i < a.size() || j < b.size(); len*=2) {
		for(int x = min((int)a.size(), i+len); i < x; i++)
			res += a[i];
		for(int y = min((int)b.size(), j+len); j < y; j++)
			res += b[j];
	}
	return res;
}
vector<stri> solve(int l, int r, vector<int> vals) {
	if(l >= r) exit(1);
	if(l+1 == r) {
		vector<stri> ans;
		for(auto i : vals) ans.push_back(stri{i});
		return ans;
	}
	if(l+2 == r) {
		vector<stri> ans;
		for(auto i : vals) {
			ans.push_back({min(i, a[l+1]), max(i, a[l+1])});
		}
		return ans;
	}
	int x = C[l];
	vals.push_back(a[l+1]);
	auto L = solve(l+1, x, vals);
	vals.push_back(a[x]);
	auto R = solve(x, r, vals);
	vals.pop_back(), vals.pop_back();
	vector<stri> ans(vals.size());
	//cout << a[l] << " " << a[l+1] << " " << a[x] << endl;
	for(int i = 0; i < vals.size(); i++) {
		ans[i] = stri{vals[i]} + mer(L.back(), R.back());
		ans[i] = min(ans[i], stri{a[l+1]} + mer(L[i], R.back()));
		ans[i] = min(ans[i], stri{a[x]} + mer(L.back(), R[i]));
		ans[i] = min(ans[i], stri{a[x]} + mer(L[i], R[R.size()-2]));
	}
	return ans;
}
 
int S = 0;
void permute(int pos) {
	if(pos > n) return;
	int os = S;
	a[S++] = B[pos-1];
	permute(2*pos);
	C[os] = S;
	permute(2*pos+1);
}
 
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i = 0; i < n; i++) cin >> B[i];
	permute(1);
	//for(int i = 0; i < n; i++) cout << a[i] << " "; cout << endl;
	auto X = solve(0, n, {a[0]})[0];
	for(auto i : X) cout << i << " "; cout << '\n';
}

Compilation message (stderr)

swap.cpp: In function 'stri mer(stri, stri)':
swap.cpp:14:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0, j = 0, len = 1; i < a.size() || j < b.size(); len*=2) {
      |                                 ~~^~~~~~~~~~
swap.cpp:14:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |  for(int i = 0, j = 0, len = 1; i < a.size() || j < b.size(); len*=2) {
      |                                                 ~~^~~~~~~~~~
swap.cpp: In function 'std::vector<std::__cxx11::basic_string<int> > solve(int, int, std::vector<int>)':
swap.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for(int i = 0; i < vals.size(); i++) {
      |                 ~~^~~~~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:70:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   70 |  for(auto i : X) cout << i << " "; cout << '\n';
      |  ^~~
swap.cpp:70:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   70 |  for(auto i : X) cout << i << " "; cout << '\n';
      |                                    ^~~~

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