oj.uz

Submission #826497

# Submission time Handle Problem Language Result Execution time Memory
826497 2023-08-15T16:01:04 Z rainboy Cheerleaders (info1cup20_cheerleaders) C
100 / 100
 400 ms 2704 KB 
#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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Correct!
2 Correct 1 ms 212 KB Correct!
3 Correct 1 ms 212 KB Correct!
4 Correct 0 ms 212 KB Correct!

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Correct!
2 Correct 0 ms 212 KB Correct!
3 Correct 0 ms 292 KB Correct!
4 Correct 0 ms 212 KB Correct!

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Correct!
2 Correct 3 ms 340 KB Correct!
3 Correct 3 ms 328 KB Correct!
4 Correct 3 ms 212 KB Correct!

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 852 KB Correct!
2 Correct 28 ms 852 KB Correct!
3 Correct 60 ms 1428 KB Correct!

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 2704 KB Correct!
2 Correct 170 ms 2588 KB Correct!
3 Correct 397 ms 2588 KB Correct!
4 Correct 400 ms 2588 KB Correct!
5 Correct 397 ms 2592 KB Correct!