Submission #388612

#	Time	Username	Problem	Language	Result	Execution time	Memory
388612		warner1129	Cheerleaders (info1cup20_cheerleaders)	C++17	100 / 100	820 ms	3656 KiB

cheerleaders

#include <bits/stdc++.h>

#define ff first
#define ss second

using namespace std;

const int maxn = 17;

pair<long long, long long> cnt[maxn];
long long ans = 0x3f3f3f3f3f3f3f;
int opt = 0, h = 0;
int n;

void dfs(int d, vector<int> vec) {
	long long c0, c1, t0, t1;
	vector<int> L, R;
	c0 = c1 = t0 = t1 = 0;
	for (int v : vec) {
		if ((v>>d) & 1) c1++, t1 += c0, R.emplace_back(v);
		else c0++, t0 += c1, L.emplace_back(v);
	}
	cnt[d].ff += t0, cnt[d].ss += t1;
	if (d--) dfs(d, L), dfs(d, R);
}

void solve() {
	cin >> n;
	ans = 1ll * (1<<n) * ((1<<n)-1) / 2;
	vector<int> vec(1<<n);
	for (int i = 0, x; i < 1<<n; i++)
		cin >> x, vec[x] = i;
	long long cntmp = 0, optmp = 0;
	for (int i = 0; i < n; i++) {
		dfs(n-1, vec);
		cntmp = optmp = 0;
		for (int j = 0; j < n; j++) {
			if (cnt[j].ff > cnt[j].ss)
				cntmp += cnt[j].ss, optmp |= (1<<((j+i)%n));
			else cntmp += cnt[j].ff;
			cnt[j] = {0, 0};
		}
		if (cntmp < ans) ans = cntmp, opt = optmp, h = i;
		for (int j = 0; j < 1<<n; j++)
			vec[j] = (vec[j]>>1) | ((vec[j]&1)<<(n-1));	
	}
	string str;
	for (int i = 0; i < n; i++) {
		str.push_back('2');
		if ((opt>>i)&1) str.push_back('1');
	}
	while (h--) str.push_back('2');
	cout << ans << '\n' << str << '\n';
}

signed main() {
	solve();
	return 0;
}

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