Submission #316954

#	Time	Username	Problem	Language	Result	Execution time	Memory
316954		jungsnow	Cheerleaders (info1cup20_cheerleaders)	C++14	100 / 100	400 ms	3512 KiB

cheerleaders

#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;
using ll = long long;

const ll oo = 1e18;
const int N = 200100;

int p[N], pos[N];
ll inv[22][2];
int n;

pair<ll, int> proc(int shifts) {
	for (int i = 0; i < (1 << n); ++i) {
		int p1 = pos[i] & ((1 << shifts) - 1);
		int p2 = pos[i] >> shifts;
		p[i] = (p1 << (n - shifts)) | p2;
	}
	vector<vector<int>> cn(n + 1);
	for (int i = 1; i <= n; ++i) cn[i].resize(1 << i);
	memset(inv, 0, sizeof inv);
	for (int i = 0; i < (1 << n); ++i) {
		for (int j = 0; j < n; ++j) {
			int others = (p[i] >> j) ^ 1;
			if (others > (p[i] >> j)) { /// 1 - 0
				inv[j][0] += cn[n - j][others];
			} else /// 0 - 1
				inv[j][1] += cn[n - j][others];
			cn[n - j][(p[i] >> j)] ++;
		}
	}
	ll xor_val = 0, res = 0;
	for (int i = 0; i < n; ++i) {
		if (inv[i][0] < inv[i][1]) res += inv[i][0];
		else res += inv[i][1], xor_val |= (1 << i);
	}
	return {res, xor_val};
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	if (n == 0) { 
		cout << 0; return 0;
	}
	for (int x, i = 0; i < (1 << n); ++i) { 
		cin >> x; pos[x] = i; 
	}
	ll ans = oo, xor_val, shifts;
	for (int i = 0; i < n; ++i) {
		pair <ll, int> res = proc(i);
		if (res.x < ans) {
			ans = res.x;
			xor_val = res.y;
			shifts = i;
		}
	}
	cout << ans << '\n';
	for (int i = 0; i < shifts; ++i) cout << '2';
	for (int i = 0; i < n; ++i) {
		cout << '2';
		if (xor_val >> i & 1) cout << '1';
	}
	return 0;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:52:24: warning: 'shifts' may be used uninitialized in this function [-Wmaybe-uninitialized]
   52 |  ll ans = oo, xor_val, shifts;
      |                        ^~~~~~
cheerleaders.cpp:65:15: warning: 'xor_val' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |   if (xor_val >> i & 1) cout << '1';
      |       ~~~~~~~~^~~~

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