#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';
}
Compilation message
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';
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
