Submission #446878

#	Time	Username	Problem	Language	Result	Execution time	Memory
446878		rainboy	Pohlepko (COCI16_pohlepko)	C11	80 / 80	233 ms	23672 KiB

pohlepko

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

#define N	2000
#define M	2000
#define A	26

int max(int a, int b) { return a > b ? a : b; }

void sort(int *aa, int *ii, int *jj, int n, int k) {
	static int kk[N + 1];
	int h, i, j, a;

	memset(kk, 0, (n + 1) * sizeof *kk);
	for (h = 0; h < k; h++) {
		i = ii[h];
		kk[aa[i] + 1]++;
	}
	for (a = 1; a <= n; a++)
		kk[a] += kk[a - 1];
	for (h = 0; h < k; h++) {
		j = ii[h];
		jj[kk[aa[j]]++] = j;
	}
}

int main() {
	static char cc[N][M + 1];
	static int aa[N][M], xx[N], yy[N], ii[N], jj[N];
	int n, m, h, i, j, k, ij;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%s", cc[i]);
	for (ij = (n - 1 + m - 1) - 1; ij >= 0; ij--) {
		k = 0;
		for (i = max(ij - (m - 1), 0), j = ij - i; i < n && j >= 0; i++, j--) {
			ii[k++] = i, xx[i] = cc[i][j] - 'a';
			yy[i] = (i + 1 < n && (j + 1 == m || aa[i + 1][j] < aa[i][j + 1])) ? aa[i + 1][j] : aa[i][j + 1];
		}
		sort(yy, ii, jj, n, k), sort(xx, jj, ii, A, k);
		for (h = 0; h < k; h++) {
			i = ii[h], j = ij - i;
			aa[i][j] = h;
		}
	}
	i = 0, j = 0;
	while (i + 1 < n || j + 1 < m) {
		printf("%c", cc[i][j]);
		if (i + 1 < n && (j + 1 == m || aa[i + 1][j] < aa[i][j + 1]))
			i++;
		else
			j++;
	}
	printf("%c\n", cc[i][j]);
	return 0;
}

Compilation message (stderr)

pohlepko.c: In function 'main':
pohlepko.c:32:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
pohlepko.c:34:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%s", cc[i]);
      |   ^~~~~~~~~~~~~~~~~~

• Subtask 1: 80 / 80