Submission #826400

#	Time	Username	Problem	Language	Result	Execution time	Memory
826400		rainboy	Cheerleaders (info1cup20_cheerleaders)	C11	54 / 100	446 ms	2592 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] += 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, h, h_, i;
	long long ans, x;

	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;
	for (h = 0; h < l; h++) {
		memcpy(aa_, aa, n * sizeof *aa), memset(kk, 0, l * sizeof *kk);
		solve(aa_, l);
		x = 0;
		for (h_ = 0; h_ < l; h_++)
			x += min(kk[h_], (1LL << l - 1 + h_) - kk[h_]);
		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);
	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 |    x += min(kk[h_], (1LL << l - 1 + h_) - kk[h_]);
      |                             ~~~~~~^~~~
cheerleaders.c:52:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   52 |    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: 8 / 16
• Subtask 2: 5 / 10
• Subtask 3: 20 / 25
• Subtask 4: 0 / 21
• Subtask 5: 21 / 28