Submission #483298

#	Time	Username	Problem	Language	Result	Execution time	Memory
483298		rainboy	Sateliti (COCI20_satellti)	C11	50 / 110	3078 ms	24900 KiB

Main

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

#define N	1000
#define M	1000

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

int aa0[N * M], aa1[N * M], hh[N * M], hh_[N * M];

void sort(int *aa, int *ii, int *jj, int n, int first) {
	static int kk[N * M + 1], kk_[N * M + 1];
	int a_ = max(n, 2) + 1, i, j, a;

	if (first) {
		memset(kk, 0, a_ * sizeof *kk);
		for (i = 0; i < n; i++) {
			a = aa[i];
			kk[a + 1]++;
		}
		for (a = 1; a < a_; a++)
			kk[a] += kk[a - 1];
		memcpy(kk_, kk, a_ * sizeof *kk);
		for (i = 0; i < n; i++) {
			j = ii[i], a = aa[j];
			jj[kk[a]++] = j;
		}
	} else {
		for (i = 0; i < n; i++) {
			j = ii[i], a = aa[j];
			jj[kk_[a]++] = j;
		}
	}
}

void compress(int *ii, int n) {
	int i, a;

	for (i = 0, a = 0; i < n; i++)
		aa0[ii[i]] = i + 1 == n || aa0[ii[i + 1]] != aa0[ii[i]] || aa1[ii[i + 1]] != aa1[ii[i]] ? a++ : a;
}

int main() {
	static char cc[N][M + 1], cc_[N][M + 1];
	int n, m, l, h, i, i_, j, j_;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++) {
		scanf("%s", cc[i]);
		for (j = 0; j < m; j++)
			aa0[i * m + j] = cc[i][j] == '*' ? 0 : 1;
	}
	for (h = 0; h < n * m; h++)
		hh_[h] = h;
	sort(aa0, hh_, hh, n * m, 1);
	for (l = 1; l < m; l <<= 1) {
		for (i = 0; i < n; i++)
			for (j = 0; j < m; j++)
				aa1[i * m + j] = aa0[i * m + (j + l) % m];
		sort(aa1, hh, hh_, n * m, 1);
		sort(aa0, hh_, hh, n * m, 0);
		compress(hh, n * m);
	}
	for (l = 1; l < n; l <<= 1) {
		for (i = 0; i < n; i++)
			for (j = 0; j < m; j++)
				aa1[i * m + j] = aa0[(i + l) % n * m + j];
		sort(aa1, hh, hh_, n * m, 1);
		sort(aa0, hh_, hh, n * m, 0);
		compress(hh, n * m);
	}
	i_ = hh[0] / m, j_ = hh[0] % m;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			cc_[i][j] = cc[(i + i_) % n][(j + j_) % m];
	for (i = 0; i < n; i++)
		printf("%s\n", cc_[i]);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 0 / 60