제출 #391076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
391076		kostia244	Swap (BOI16_swap)	C++17	0 / 100	1 ms	332 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;
}
bool cmp(const int &x, const stri &y, const stri &z, const int &a, const stri &b, const stri &c) {
	if(x != a) return x < a;
	for(int i = 0, j = 0, len = 1; i < y.size() || j < z.size(); len*=2) {
		for(int T = min((int)y.size(), i+len); i < T; i++)
			if(y[i] != b[i]) return y[i] < b[i];
		for(int T = min((int)z.size(), j+len); j < T; j++)
			if(z[j] != c[j]) return z[j] < c[j];
	}
	return 0;
}
int sum = 0;
vector<stri> solve(int l, int r, vector<int> vals) {
	if(l >= r) exit(1);
	if(l+1 == r) {
		sum++;
		vector<stri> ans;
		for(auto i : vals) ans.push_back(stri{i});
		return ans;
	}
	if(l+2 == r) {
		sum++;
		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++) {
		bool A = cmp(vals[i], L.back(), R.back(), a[l+1], L[i], R.back());
		bool B = cmp(a[x], L.back(), R[i], a[x], L[i], R[R.size()-2]);
		bool C = cmp(A ? vals[i] : a[l+1], A ? L.back() : L[i], R.back(),
					 a[x], B ? L.back() : L[i], B ? R[i] : R[R.size()-2]);
		if(C) {
			if(A)
			ans[i] = stri{vals[i]} + mer(L.back(), R.back());
			else
			ans[i] = min(ans[i], stri{a[l+1]} + mer(L[i], R.back()));
		} else {
			if(B)
			ans[i] = min(ans[i], stri{a[x]} + mer(L.back(), R[i]));
			else
			ans[i] = min(ans[i], stri{a[x]} + mer(L[i], R[R.size()-2]));
		}
		sum+=ans[i].size();
	}
	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';
	cerr << sum << '\n';
}

컴파일 시 표준 에러 (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 'bool cmp(const int&, const stri&, const stri&, const int&, const stri&, const stri&)':
swap.cpp:24:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i = 0, j = 0, len = 1; i < y.size() || j < z.size(); len*=2) {
      |                                 ~~^~~~~~~~~~
swap.cpp:24:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for(int i = 0, j = 0, len = 1; i < y.size() || j < z.size(); len*=2) {
      |                                                 ~~^~~~~~~~~~
swap.cpp: In function 'std::vector<std::__cxx11::basic_string<int> > solve(int, int, std::vector<int>)':
swap.cpp:57:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i = 0; i < vals.size(); i++) {
      |                 ~~^~~~~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:95:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   95 |  for(auto i : X) cout << i << " "; cout << '\n';
      |  ^~~
swap.cpp:95:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   95 |  for(auto i : X) cout << i << " "; cout << '\n';
      |                                    ^~~~

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