#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<<17;
const ll inf = 1ll<<60;
int n, a[maxn], B[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) {
//cout << l << " " << r << endl;
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 = B[l];
//cout << l << " -> " << B[l] << endl;
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());
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;
a[S++] = B[pos-1];
int os = S;
permute(2*pos);
B[os-1] = 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
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:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i = 0; i < vals.size(); i++) {
| ~~^~~~~~~~~~~~~
swap.cpp: In function 'int main()':
swap.cpp:71:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
71 | for(auto i : X) cout << i << " "; cout << '\n';
| ^~~
swap.cpp:71:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
71 | for(auto i : X) cout << i << " "; cout << '\n';
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
