Submission #1145707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145707		Agageldi	Cheerleaders (info1cup20_cheerleaders)	C++20	26 / 100	2078 ms	457584 KiB

cheerleaders

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

#define ll long long
#define N 2000
#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 * (1LL),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))]);
		}
	}
	solve(op % 2 + 1, 1, san + 1);
	if(sany < 2) 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';
}

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