#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define gcd __gcd
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define rep(i, n) for (int i=0; i<(n); i++)
#define rep1(i, n) for (int i=1; i<=(n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define endl "\n"
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
template<typename T, typename cmp = less<T>>
using ordered_set = tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
typedef trie<string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
constexpr int N = 2e5 + 5;
int n;
int a[N];
vector<int> idx[N];
vector<int> rsv[N];
vector<int> merge(const vector<int>& a, const vector<int>& b, int i) {
auto& l = idx[i * 2], r = idx[i * 2 + 1];
vector<int> ans;
int p = 0, q = 0;
while(p < l.size() || q < r.size()) {
if(p == l.size() || (q != r.size() && r[q] < l[p])) ans.pb(b[q++]);
else ans.pb(a[p++]);
}
return ans;
}
int cnt = 0;
vector<int> solve(int i) {
cnt++;
if(i > n) return {};
if(i * 2 > n) return vi{a[i]};
if(i * 2 == n) {
return vi{min(a[i], a[i * 2]), max(a[i], a[i * 2])};
}
if(i * 4 > n) {
int x = a[i], y = a[i * 2], z = a[i * 2 + 1];
if(x < y && x < z) return vi{x, y, z};
else if(y < x && y < z) return vi{y, x, z};
else return vi{z, min(x, y), max(x, y)};
}
if(a[i] < a[i * 2] && a[i] < a[i * 2 + 1]) {
vector<int> ans = merge(solve(i * 2), solve(i * 2 + 1), i);
ans.insert(ans.begin(), a[i]);
return ans;
}
else if(a[i * 2] < a[i] && a[i * 2] < a[i * 2 + 1]) {
swap(a[i], a[i * 2]);
vector<int> ans = merge(solve(i * 2), solve(i * 2 + 1), i);
ans.insert(ans.begin(), a[i]);
return ans;
}
else {
swap(a[i], a[i * 2 + 1]);
rsv[i].clear();
for(int j: idx[i]) rsv[i].pb(a[j]);
vector<int> ans = merge(solve(i * 2), solve(i * 2 + 1), i);
for(int j = 0; j < idx[i].size(); j++) {
a[idx[i][j]] = rsv[i][j];
}
swap(a[i * 2], a[i * 2 + 1]);
vector<int> ans2 = merge(solve(i * 2), solve(i * 2 + 1), i);
if(ans2 < ans) ans.swap(ans2);
ans.insert(ans.begin(), a[i]);
return ans;
}
}
int32_t main() {
fastio;
cin >> n;
for(int i = n; i >= 1; i--) {
idx[i].pb(i);
if(2 * i < n) {
int p = 0, q = 0;
auto &a = idx[2 * i], &b = idx[2 * i + 1];
while(p < a.size() || q < b.size()) {
if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
else idx[i].pb(a[p++]);
}
}
else if(2 * i == n) {
idx[i].insert(idx[i].end(), all(idx[2 * i]));
}
}
//for(int i = 1; i <= n; i++) a[i] = i;
//reverse(a + 1, a + 1 + n);
//random_shuffle(a + 1, a + 1 + n);
for(int i = 1; i <= n; i++) cin >> a[i];
auto ans = solve(1);
cout << cnt << endl;
for(int x: ans) cout << x << ' '; cout << endl;
}
Compilation message
swap.cpp: In function 'std::vector<int> merge(const std::vector<int>&, const std::vector<int>&, int)':
swap.cpp:56:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | while(p < l.size() || q < r.size()) {
| ~~^~~~~~~~~~
swap.cpp:56:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
56 | while(p < l.size() || q < r.size()) {
| ~~^~~~~~~~~~
swap.cpp:57:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | if(p == l.size() || (q != r.size() && r[q] < l[p])) ans.pb(b[q++]);
| ~~^~~~~~~~~~~
swap.cpp:57:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | if(p == l.size() || (q != r.size() && r[q] < l[p])) ans.pb(b[q++]);
| ~~^~~~~~~~~~~
swap.cpp: In function 'std::vector<int> solve(int)':
swap.cpp:93:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int j = 0; j < idx[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
swap.cpp: In function 'int32_t main()':
swap.cpp:112:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | while(p < a.size() || q < b.size()) {
| ~~^~~~~~~~~~
swap.cpp:112:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
112 | while(p < a.size() || q < b.size()) {
| ~~^~~~~~~~~~
swap.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
| ~~^~~~~~~~~~~
swap.cpp:113:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | if(p == a.size() || (q != b.size() && b[q] < a[p])) idx[i].pb(b[q++]);
| ~~^~~~~~~~~~~
swap.cpp:127:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
127 | for(int x: ans) cout << x << ' '; cout << endl;
| ^~~
swap.cpp:127:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
127 | for(int x: ans) cout << x << ' '; cout << endl;
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
