oj.uz

Submission #904063

# Submission time Handle Problem Language Result Execution time Memory
904063 2024-01-11T19:17:58 Z rainboy Shifty Grid (CCO17_shifty) C
25 / 25
 9 ms 1636 KB 
#include <stdio.h>

#define N	100
#define M	100
#define K	(N * M * 4 + 1)

int aa[N][M], ii[N * M], jj[N * M], n, m;

int tt[K], hh[K], dd[K], k;

void rotate(int i1, int j1, int i2, int j2, int cw) {
	int di, dj, a, b, c;

	di = (i2 - i1 + n) % n, dj = (j2 - j1 + m) % m;
	if (cw) {
		tt[k] = 2, hh[k] = j1, dd[k] = n - di, k++;
		tt[k] = 1, hh[k] = i1, dd[k] = m - dj, k++;
		tt[k] = 2, hh[k] = j1, dd[k] = di, k++;
		tt[k] = 1, hh[k] = i1, dd[k] = dj, k++;
		a = aa[i1][j1], b = aa[i1][j2], c = aa[i2][j1];
		aa[i1][j1] = c, ii[c] = i1, jj[c] = j1;
		aa[i1][j2] = a, ii[a] = i1, jj[a] = j2;
		aa[i2][j1] = b, ii[b] = i2, jj[b] = j1;
	} else {
		tt[k] = 1, hh[k] = i1, dd[k] = m - dj, k++;
		tt[k] = 2, hh[k] = j1, dd[k] = n - di, k++;
		tt[k] = 1, hh[k] = i1, dd[k] = dj, k++;
		tt[k] = 2, hh[k] = j1, dd[k] = di, k++;
		a = aa[i1][j1], b = aa[i1][j2], c = aa[i2][j1];
		aa[i1][j1] = b, ii[b] = i1, jj[b] = j1;
		aa[i1][j2] = c, ii[c] = i1, jj[c] = j2;
		aa[i2][j1] = a, ii[a] = i2, jj[a] = j1;
	}
}

int main() {
	static char visited[N * M];
	int h, i, j, a, c, tmp;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			scanf("%d", &a);
			aa[i][j] = a, ii[a] = i, jj[a] = j;
		}
	c = 0;
	for (a = 0; a < n * m; a++)
		if (!visited[a]) {
			c++;
			while (!visited[a])
				visited[a] = 1, a = ii[a] * m + jj[a];
		}
	if (c % 2 != 0) {
		tt[k] = 1, hh[k] = 0, dd[k] = 1, k++;
		for (j = m - 1; j > 0; j--)
			tmp = aa[0][j], aa[0][j] = aa[0][j - 1], aa[0][j - 1] = tmp;
		for (j = 0; j < m; j++)
			jj[aa[0][j]] = j;
	}
	for (i = 0; i + 2 < n; i++)
		for (j = 0; j < m; j++) {
			a = i * m + j;
			if (ii[a] == i && jj[a] == j)
				continue;
			if (ii[a] == i)
				rotate(i, j, i + 1, jj[a], 0);
			else if (jj[a] != j)
				rotate(ii[a], j, i, jj[a], 1);
			else
				rotate(ii[a], j, i, j ^ 1, 0);
		}
	for (j = 0; j + 1 < m; j++)
		for (i = n - 2; i < n; i++) {
			a = i * m + j;
			if (ii[a] == i && jj[a] == j)
				continue;
			if (jj[a] == j)
				rotate(i, j, ii[a], j + 1, 1);
			else if (ii[a] != i)
				rotate(i, jj[a], ii[a], j, 0);
			else
				rotate(i, jj[a], i ^ 1, j, 1);
		}
	printf("%d\n", k);
	for (h = 0; h < k; h++)
		printf("%d %d %d\n", tt[h], hh[h] + 1, dd[h]);
	return 0;
}

Compilation message

Main.c: In function 'main':
Main.c:40:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:43:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |    scanf("%d", &a);
      |    ^~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 0 ms 360 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 0 ms 360 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 0 ms 360 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 0 ms 360 KB Output is correct
11 Correct 0 ms 360 KB Output is correct
12 Correct 0 ms 432 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 360 KB Output is correct
2 Correct 0 ms 360 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 360 KB Output is correct
5 Correct 1 ms 360 KB Output is correct
6 Correct 7 ms 1180 KB Output is correct
7 Correct 9 ms 1128 KB Output is correct
8 Correct 9 ms 1128 KB Output is correct
9 Correct 1 ms 608 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 360 KB Output is correct
2 Correct 0 ms 360 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 0 ms 360 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 0 ms 360 KB Output is correct
9 Correct 1 ms 360 KB Output is correct
10 Correct 0 ms 360 KB Output is correct
11 Correct 0 ms 360 KB Output is correct
12 Correct 0 ms 432 KB Output is correct
13 Correct 1 ms 360 KB Output is correct
14 Correct 0 ms 360 KB Output is correct
15 Correct 0 ms 360 KB Output is correct
16 Correct 0 ms 360 KB Output is correct
17 Correct 1 ms 360 KB Output is correct
18 Correct 7 ms 1180 KB Output is correct
19 Correct 9 ms 1128 KB Output is correct
20 Correct 9 ms 1128 KB Output is correct
21 Correct 1 ms 608 KB Output is correct
22 Correct 2 ms 604 KB Output is correct
23 Correct 7 ms 1116 KB Output is correct
24 Correct 5 ms 1112 KB Output is correct
25 Correct 5 ms 860 KB Output is correct
26 Correct 1 ms 608 KB Output is correct
27 Correct 6 ms 1128 KB Output is correct
28 Correct 7 ms 1384 KB Output is correct
29 Correct 9 ms 1384 KB Output is correct
30 Correct 7 ms 1636 KB Output is correct
31 Correct 7 ms 1384 KB Output is correct
32 Correct 7 ms 1376 KB Output is correct
33 Correct 3 ms 444 KB Output is correct
34 Correct 2 ms 604 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 5 ms 1116 KB Output is correct
37 Correct 1 ms 552 KB Output is correct
38 Correct 2 ms 604 KB Output is correct
39 Correct 3 ms 604 KB Output is correct
40 Correct 4 ms 604 KB Output is correct
41 Correct 2 ms 604 KB Output is correct
42 Correct 1 ms 604 KB Output is correct
43 Correct 5 ms 860 KB Output is correct
44 Correct 1 ms 348 KB Output is correct
45 Correct 5 ms 868 KB Output is correct
46 Correct 4 ms 864 KB Output is correct