Submission #826497

#	Time	Username	Problem	Language	Result	Execution time	Memory
826497		rainboy	Cheerleaders (info1cup20_cheerleaders)	C11	100 / 100	400 ms	2704 KiB

cheerleaders

#include <stdio.h>
#include <string.h>

#define L	17
#define N	(1 << L)
#define INF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }

long long kk[L];

void solve(int *aa, int l) {
	if (l) {
		static int bb[N];
		int n, m, i, j, k;

		n = 1 << l, m = n >> 1;
		solve(aa, l - 1), solve(aa + m, l - 1);
		for (i = 0, j = m; j < n; j++) {
			while (i < m && aa[i] < aa[j])
				i++;
			kk[l - 1] += m - i;
		}
		i = 0, j = m, k = 0;
		while (i < m || j < n)
			bb[k++] = j == n || i < m && aa[i] < aa[j] ? aa[i++] : aa[j++];
		memcpy(aa, bb, n * sizeof *bb);
	}
}

int main() {
	static int aa[N], aa_[N];
	int n, l, r, r_, h, i, b, b_;
	long long k0, k1, x, ans;

	scanf("%d", &l), n = 1 << l;
	if (l == 0) {
		printf("0\n");
		return 0;
	}
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	ans = INF, r_ = -1, b_ = 0;
	for (r = 0; r < l; r++) {
		memcpy(aa_, aa, n * sizeof *aa), memset(kk, 0, l * sizeof *kk);
		solve(aa_, l);
		x = 0, b = 0;
		for (h = 0; h < l; h++) {
			k0 = kk[h], k1 = (1LL << l + h - 1) - k0;
			if (k0 < k1)
				x += k0;
			else
				x += k1, b |= 1 << h;
		}
		if (ans > x)
			ans = x, r_ = r, b_ = b;
		ans = min(ans, x);
		for (i = 0; i < n; i++)
			aa_[i >> 1 | (i & 1) << l - 1] = aa[i];
		memcpy(aa, aa_, n * sizeof *aa_);
	}
	printf("%lld\n", ans);
	for (r = 0; r < r_; r++)
		printf("2");
	for (h = 0; h < l; h++) {
		if ((b_ & 1 << (h + l - 1) % l) != 0)
			printf("1");
		printf("2");
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

cheerleaders.c: In function 'solve':
cheerleaders.c:26:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   26 |    bb[k++] = j == n || i < m && aa[i] < aa[j] ? aa[i++] : aa[j++];
      |                        ~~~~~~^~~~~~~~~~~~~~~~
cheerleaders.c: In function 'main':
cheerleaders.c:49:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   49 |    k0 = kk[h], k1 = (1LL << l + h - 1) - k0;
      |                             ~~~~~~^~~
cheerleaders.c:59:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   59 |    aa_[i >> 1 | (i & 1) << l - 1] = aa[i];
      |                            ~~^~~
cheerleaders.c:36:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  scanf("%d", &l), n = 1 << l;
      |  ^~~~~~~~~~~~~~~
cheerleaders.c:42:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~

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