Submission #1145750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145750		Agageldi	Cheerleaders (info1cup20_cheerleaders)	C++20	21 / 100	2095 ms	4572 KiB

cheerleaders

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 200000
#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);
	if(!ans) {
		cout << '0' << '\n';
		for(auto i:v) {
			cout <<i;
		}
		exit(0);
	}
}

void solve(int op,int sany,int san,int bal) {
	if(bal == 1 && san > 2*n || san > n*3) 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))]);
		}
	}
	if(sany + 1 < n && op == 2) solve(op, sany + 1, san + 1,bal);
	solve(op % 2 + 1, 0, san + 1,bal);
}

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,1);
	if(ans == INT_MAX) ans = 0;
	v.clear();
	solve(1,0,0,0);
	cout << ans << '\n';
	if(!sz(ansv)) {
		cout <<"11";
	}
	for(auto i:ansv) {
		cout << i;
	}
	cout << '\n';
}

• Subtask 1: 16 / 16
• Subtask 2: 5 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 21
• Subtask 5: 0 / 28