Submission #316927

#	Time	Username	Problem	Language	Result	Execution time	Memory
316927		jungsnow	Cheerleaders (info1cup20_cheerleaders)	C++14	26 / 100	2086 ms	35340 KiB

cheerleaders

#include<bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<vi, int> vii;

int n, ans;
map <vi, vii> pre;
map <vi, bool> mp;

vi swap(vi &a) {
	vi b(1 << n);
	for (int i = 0; i < (1 << n); ++i) {
		b[i] = a[i ^ (1 << n - 1)];
	}
	return b;
}

vi split(vi &a) {
	vi b(1 << n);
	for (int i = 0; i < (1 << n); ++i) {
		int ni = i >> 1;
		if (i & 1) ni |= (1 << n - 1);
		else ni &= (1 << n - 1) - 1;
		b[ni] = a[i];
	}
	return b;
}

int inv(vi &a) {
	int cn = 0;
	for (int i = 0; i < (1 << n); ++i) {
		for (int j = i + 1; j < (1 << n); ++j) {
			cn += (a[i] > a[j]);
		}
	}
	return cn;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	if (n == 0) {
		cout << 0 << '\n';
		return 0;
	}
	vi a(1 << n);
	for (int i = 0; i < (1 << n); ++i) {
		cin >> a[i];
	}
	ans = inv(a); vi res;
	queue <vi> q; q.push(a);
	mp[a] = true;
	while (q.size()) {
		vi c = q.front(); q.pop();
		vi d = split(c);
		if (!mp.count(d)) {
			mp[d] = true;
			int tm = inv(d);
			if (tm < ans) {
				ans = tm;
				res = d;
			}
			pre[d] = vii(c, 2);
			q.push(d);
		}
		d = swap(c);
		if (!mp.count(d)) {
			mp[d] = true;
			int tm = inv(d);
			if (tm < ans) {
				ans = tm;
				res = d;
			}
			pre[d] = vii(c, 1);
			q.push(d);
		}
	}
	cout << ans << '\n';
	vector <int> vec;
	while (pre.count(res)) {
		vec.push_back(pre[res].second);
		res = pre[res].first;
	}
	reverse(vec.begin(), vec.end());
	for (int x : vec) cout << x;
	return 0;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'vi swap(vi&)':
cheerleaders.cpp:15:24: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   15 |   b[i] = a[i ^ (1 << n - 1)];
      |                      ~~^~~
cheerleaders.cpp: In function 'vi split(vi&)':
cheerleaders.cpp:24:28: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   24 |   if (i & 1) ni |= (1 << n - 1);
      |                          ~~^~~
cheerleaders.cpp:25:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   25 |   else ni &= (1 << n - 1) - 1;
      |                    ~~^~~

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