// #include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <random>
#include <iostream>
#include <ctime>
#pragma GCC optimize("Ofast", "unroll-loops", "no-stack-protector")
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 17;
int a[1 << N];
vi who[N][1 << N];
signed main()
{
IO_OP;
int n;
cin >> n;
// n = 17;
if(n == 0){
cout << 0 << endl;
cout << endl;
return 0;
}
for(int i = 0; i < (1 << n); i++) {
int x;
cin >> x;
// x = i;
a[x] = i;
}
// mt19937 rng(time(0));
// shuffle(a, a + (1 << n), rng);
auto shift_right = [&]() {
cout << 2;
};
auto flip_bit = [&](int bit) {
for(int i = 0; i < bit + 1; i++) shift_right();
cout << 1;
for(int i = 0; i < n - bit - 1; i++) shift_right();
};
auto xor_val = [&](int val) {
for(int i = 0; i < n; i++) if(val >> i & 1)
flip_bit(i);
};
ll best_inv = 1e18, best_shift = 0, best_xor = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < (1 << (n - i)); j++)
who[i][j].reserve(1 << i);
for(int shift = 0; shift < n; shift++) {
for(int i = 0; i < n; i++)
for(int j = 0; j < (1 << (n - i)); j++)
who[i][j].clear();
for(int j = 0; j < (1 << n); j++)
for(int i = 0; i < n; i++)
who[i][a[j] >> i].PB(j);
auto count_inv = [&](vi& a, vi& b) {
ll ans = 0;
for(int i = 0, j = 0; i < a.size(); i++) {
while(j < b.size() && b[j] < a[i]) j++;
ans += j;
}
return ans;
};
ll val = 0, inv = 0;
for(int i = 0; i < n; i++) {
ll one = 0, zero = 0;
for(int prefix = 0; prefix < (1 << (n - i)); prefix += 2) {
int mask1 = prefix, mask2 = prefix + 1;
ll cur_zero = count_inv(who[i][mask1], who[i][mask2]);
// ll cur_one = count_inv(who[mask2][i], who[mask1][i]);
ll cur_one = (1LL << i << i) - cur_zero; // const opt
one += cur_one, zero += cur_zero;
}
if(one < zero) val |= 1 << i;
inv += min(one, zero);
if(inv > best_inv) break; // const opt
}
if(inv < best_inv) {
best_inv = inv;
best_shift = shift;
best_xor = val;
}
for(int i = 0; i < (1 << n); i++)
a[i] = (a[i] >> 1) | ((a[i] & 1) << (n - 1)); // shift right
}
cout << best_inv << endl;
for(int i = 0; i < best_shift; i++) shift_right();
xor_val(best_xor);
cout << endl;
}
Compilation message
cheerleaders.cpp: In lambda function:
cheerleaders.cpp:75:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(int i = 0, j = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
cheerleaders.cpp:76:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | while(j < b.size() && b[j] < a[i]) j++;
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
52716 KB |
Correct! |
2 |
Correct |
35 ms |
52716 KB |
Correct! |
3 |
Correct |
35 ms |
52716 KB |
Correct! |
4 |
Correct |
34 ms |
52716 KB |
Correct! |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
52736 KB |
Correct! |
2 |
Correct |
35 ms |
52716 KB |
Correct! |
3 |
Correct |
34 ms |
52716 KB |
Correct! |
4 |
Correct |
36 ms |
52716 KB |
Correct! |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
39 ms |
52844 KB |
Correct! |
2 |
Correct |
40 ms |
52844 KB |
Correct! |
3 |
Correct |
40 ms |
52972 KB |
Correct! |
4 |
Correct |
40 ms |
52844 KB |
Correct! |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
137 ms |
56300 KB |
Correct! |
2 |
Correct |
146 ms |
56300 KB |
Correct! |
3 |
Correct |
290 ms |
60268 KB |
Correct! |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
755 ms |
68204 KB |
Correct! |
2 |
Correct |
778 ms |
68332 KB |
Correct! |
3 |
Correct |
1624 ms |
68204 KB |
Correct! |
4 |
Correct |
1588 ms |
68332 KB |
Correct! |
5 |
Correct |
1641 ms |
68972 KB |
Correct! |