Submission #1146633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146633		stdfloat	Cheerleaders (info1cup20_cheerleaders)	C++20	51 / 100	2095 ms	2956 KiB

cheerleaders

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

using ll = long long;

const int p = 31, md = (int)1e5 + 3;

int n, X, Y, mn = INT_MAX;

vector<bool> op, ans, vis(md + 1);

vector<int> a, v, pw, fn;

void f() {
	for (int i = 0; i < 2; i++) {
		if (!i) {
			if (!op.empty() && !op.back()) continue;

			for (int j = 0; j < Y; j++)
				swap(a[j], a[j + Y]);
		}
		else {
			if ((int)op.size() >= n && !count(op.end() - n, op.end(), 0)) continue;

			v = a;
			for (int j = 0; j < X; j++) {
				if (!(j & 1)) v[j >> 1] = a[j];
				else v[Y + (j >> 1)] = a[j];
			}

			a = v;
		}

		op.push_back(i);

		int sm = 0;
		for (int i = 0; i < X; i++)
			sm = (sm + a[i] * pw[i] % md) % md;

		if (!vis[sm]) {
			vis[sm] = true;

			int cnt = 0;
			fn.assign(X + 1, 0);
			for (int j = X - 1; j >= 0 && cnt < mn; j--) {
				for (int k = a[j]; k > 0; k -= k & -k)
					cnt += fn[k];
				for (int k = a[j] + 1; k <= X; k += k & -k)
					fn[k]++;
			}

			if (cnt < mn) {
				ans = op;
				mn = cnt;
			}

			f();
		}
		op.pop_back();
	
		if (!i) {
			for (int j = 0; j < Y; j++)
				swap(a[j], a[j + Y]);
		}
		else {
			v = a;
			for (int j = 0; j < X; j++) {
				if (j < Y) a[j << 1] = v[j];
				else a[((j - Y) << 1) + 1] = v[j];
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n;

	X = 1 << n;
	Y = 1 << (n - 1);
	a.assign(X, 0);
	for (auto &i : a)
		cin >> i;

	pw.assign(X, 1);
	for (int i = 1; i < n; i++)
		pw[i] = pw[i - 1] * p % md;

	v.assign(X, 0);
	f();

	cout << mn << endl;
	for (auto i : ans)
		cout << i + 1;
}

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