Submission #483193

#	Time	Username	Problem	Language	Result	Execution time	Memory
483193		rk42745417	Cheerleaders (info1cup20_cheerleaders)	C++17	54 / 100	300 ms	11024 KiB

cheerleaders

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

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(0);
using ll = int64_t;
using uint = uint32_t;
using ull = uint64_t;
using ld = long double;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-8;
const ll LINF = ll(1e18) + ll(1e15);
static auto LamyIsCute = []() {
	EmiliaMyWife
		return 48763;
}();

signed main() {
	int n;
	cin >> n;
	if(n == 0) {
		cout << "0\n";
		return 0;
	}
	auto rot = [&](int &a) {
		a = (a >> 1) | ((a & 1) << (n - 1));
	};
	vector<int> arr(1 << n);
	for(int i = 0; i < (1 << n); i++) {
		int x;
		cin >> x;
		arr[x] = i;
	}

	int a, b;
	ll mn = LINF;
	for(int i = 0; i < n; i++) {
		//for(int x : arr)
			//cout << x << ' ';
		//cout << '\n';
		ll res = 0;
		int w = 0;

		vector<vector<ll>> cost(n, vector<ll>(2));
		vector<vector<int>> cnt(n, vector<int>(1 << n));
		for(int j = 0; j < (1 << n); j++) {
			for(int k = 0; k < n; k++) {
				int r = arr[j] >> k;
				cost[k][r & 1] += cnt[k][r ^ 1];
			}
			for(int k = 0; k < n; k++)
				cnt[k][arr[j] >> k]++;
		}
		for(int i = 0; i < n; i++) {
			if(cost[i][1] < cost[i][0])
				w ^= 1 << i;
			res += min(cost[i][1], cost[i][0]);
		}

		if(res < mn) {
			mn = res;
			a = i;
			b = w;
		}
		for(int &x : arr)
			rot(x);
	}
	string s(a, '2');
	for(int i = 0, w = 0; i < n; i++) {
		if(b >> w & 1)
			s += '1';
		s += '2';
		w = (w - 1 + n) % n;
	}
	cout << mn << '\n' << s << '\n';
}

Compilation message (stderr)

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:70:8: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |   if(b >> w & 1)
      |      ~~^~~~
cheerleaders.cpp:68:17: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |  string s(a, '2');
      |                 ^

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