| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1145704 | Agageldi | Cheerleaders (info1cup20_cheerleaders) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 20005
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sz(s) (int)s.size()
#define pii pair<int,int>
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll b[N], n, a[N], c[N], t, cnt = 0, ans = LLONG_MAX, fn[N], dp[3][N];
vector <int> v, ansv;
int find(int x) {
int sum = 0;
while(x <= (1LL << n)) {
sum += fn[x];
x += (x&(-x));
}
return sum;
}
void upd(int x) {
while(x > 0) {
fn[x]++;
x -= (x&(-x));
}
}
void rem(int x) {
while(x > 0) {
fn[x] = 0;
x -= (x&(-x));
}
}
void check() {
ll bal = 0, tr = 0;
for(int i = 1; i <= (1LL << n); i++) {
if(b[i] <= 1) {
bal += (i - 1);
if(!b[i]) tr = 1;
else bal -= tr;
continue;
}
int pp = find(b[i]);
bal += pp;
upd(b[i]);
}
for(int i = 1; i <= (1LL<<n) ;i++) {
if(b[i] <= 1) continue;
rem(b[i]);
}
if(ans > bal) ansv = v;
ans = min(bal,ans);
}
void solve(int op,int sany,int san) {
if(san > min(N,n*5)) return;
check();
if(op == 2) {
v.pb(2);
cnt = 1;
for(int i = 1; i <= (1LL<<n); i += 2) {
c[cnt] = b[i];
cnt++;
}
for(int i = 2; i <= (1LL<<n); i += 2){
c[cnt] = b[i];
cnt++;
}
for(int i = 1; i <= (1LL<<n); i++) {
b[i] = c[i];
}
}
if(op == 1) {
v.pb(1);
for(int i = 1; i <= (1LL << (n - 1)); i++) {
swap(b[i],b[i + (1LL << (n - 1))]);
}
}
solve(op % 2 + 1, 1, san + 1);
if(sany < n - 1) solve(op, sany + 1, san + 1);
}
int main () {
ios::sync_with_stdio(0);cin.tie(0);
cin >> n;
for(int i = 1; i <= (1LL << n); i++) {
cin >> a[i];
b[i] = a[i];
}
solve(2,0,0);
if(ans == INT_MAX) ans = 0;
cout << ans << '\n';
if(!sz(ansv)) {
cout <<"11";
}
for(auto i:ansv) {
cout << i;
}
cout << '\n';
}