oj.uz

Submission #826400

# Submission time Handle Problem Language Result Execution time Memory
826400 2023-08-15T14:25:28 Z rainboy Cheerleaders (info1cup20_cheerleaders) C
54 / 100
 446 ms 2592 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] += 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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Correct!
2 Correct 1 ms 212 KB Correct number of inversions, wrong sequence of operations
3 Correct 0 ms 212 KB Correct number of inversions, wrong sequence of operations
4 Correct 0 ms 212 KB Correct number of inversions, wrong sequence of operations

Subtask #2
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Correct number of inversions, wrong sequence of operations
2 Correct 0 ms 212 KB Correct number of inversions, wrong sequence of operations
3 Correct 0 ms 292 KB Correct number of inversions, wrong sequence of operations
4 Correct 0 ms 288 KB Correct number of inversions, wrong sequence of operations

Subtask #3
20.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Correct number of inversions, wrong sequence of operations
2 Correct 3 ms 212 KB Correct number of inversions, wrong sequence of operations
3 Correct 3 ms 212 KB Correct number of inversions, wrong sequence of operations
4 Correct 3 ms 340 KB Correct number of inversions, wrong sequence of operations

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 852 KB Correct number of inversions, wrong sequence of operations
2 Halted 0 ms 0 KB -

Subtask #5
21.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 2592 KB Correct number of inversions, wrong sequence of operations
2 Correct 174 ms 2592 KB Correct number of inversions, wrong sequence of operations
3 Correct 446 ms 2584 KB Correct number of inversions, wrong sequence of operations
4 Correct 399 ms 2592 KB Correct number of inversions, wrong sequence of operations
5 Correct 392 ms 2504 KB Correct number of inversions, wrong sequence of operations