oj.uz

Submission #869840

# Submission time Handle Problem Language Result Execution time Memory
869840 2023-11-05T21:36:55 Z rainboy Cat (info1cup19_cat) C
100 / 100
 355 ms 20824 KB 
#include <stdio.h>

#define N	3000000

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		static int aa[N], uu[N * 2], vv[N * 2];
		static char flipped[N];
		int n, cnt, h, i, j, p, good, tmp;

		scanf("%d", &n), n /= 2;
		for (i = 0; i < n * 2; i++)
			scanf("%d", &aa[i]), aa[i]--;
		good = 1;
		for (i = 0; i < n; i++)
			if (aa[i] + aa[n * 2 - 1 - i] != n * 2 - 1) {
				good = 0;
				break;
			}
		if (!good) {
			printf("-1\n");
			continue;
		}
		good = 1;
		for (i = 0; i < n; i++)
			if ((flipped[i] = aa[i] > aa[n * 2 - 1 - i])) {
				good ^= 1;
				aa[i] = aa[n * 2 - 1 - i];
			}
		if (!good) {
			printf("-1\n");
			continue;
		}
		cnt = 0;
		for (i = 0, p = -1; i < n; i++) {
			while ((j = aa[i]) != i) {
				tmp = aa[i], aa[i] = aa[j], aa[j] = tmp;
				if (!flipped[i])
					uu[cnt] = i, vv[cnt] = j, cnt++;
				else
					uu[cnt] = i, vv[cnt] = n * 2 - 1 - j, cnt++;
				flipped[i] ^= flipped[j], flipped[j] = 0;
			}
			if (flipped[i]) {
				if (p == -1)
					p = i;
				else {
					uu[cnt] = i, vv[cnt] = p, cnt++;
					uu[cnt] = i, vv[cnt] = n * 2 - 1 - p, cnt++;
					p = -1;
				}
			}
		}
		printf("%d %d\n", cnt, cnt);
		for (h = 0; h < cnt; h++)
			printf("%d %d\n", uu[h] + 1, vv[h] + 1);
	}
	return 0;
}

Compilation message

cat.c: In function 'main':
cat.c:8:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |  scanf("%d", &t);
      |  ^~~~~~~~~~~~~~~
cat.c:14:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |   scanf("%d", &n), n /= 2;
      |   ^~~~~~~~~~~~~~~
cat.c:16:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |    scanf("%d", &aa[i]), aa[i]--;
      |    ^~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6748 KB Output is correct
2 Correct 17 ms 6744 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB Output is correct
2 Correct 17 ms 6748 KB Output is correct
3 Correct 17 ms 6744 KB Output is correct
4 Correct 19 ms 6748 KB Output is correct
5 Correct 8 ms 6612 KB Output is correct
6 Correct 6 ms 6744 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6748 KB Output is correct
2 Correct 17 ms 6744 KB Output is correct
3 Correct 334 ms 15368 KB Output is correct
4 Correct 324 ms 18804 KB Output is correct
5 Correct 346 ms 20660 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB Output is correct
2 Correct 17 ms 6748 KB Output is correct
3 Correct 17 ms 6744 KB Output is correct
4 Correct 19 ms 6748 KB Output is correct
5 Correct 8 ms 6612 KB Output is correct
6 Correct 6 ms 6744 KB Output is correct
7 Correct 334 ms 15368 KB Output is correct
8 Correct 324 ms 18804 KB Output is correct
9 Correct 346 ms 20660 KB Output is correct
10 Correct 352 ms 15184 KB Output is correct
11 Correct 317 ms 13272 KB Output is correct
12 Correct 332 ms 19228 KB Output is correct
13 Correct 355 ms 20824 KB Output is correct
14 Correct 330 ms 19004 KB Output is correct