oj.uz

Submission #869839

# Submission time Handle Problem Language Result Execution time Memory
869839 2023-11-05T21:36:13 Z rainboy Cat (info1cup19_cat) C
55 / 100
 392 ms 35468 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] = n * 2 - 1 - 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
6.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB Correct number of moves

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7256 KB Output is correct
2 Correct 19 ms 7260 KB Output is correct

Subtask #3
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB Correct number of moves
2 Correct 17 ms 7256 KB Output is correct
3 Correct 19 ms 7260 KB Output is correct
4 Correct 19 ms 7260 KB Correct number of moves
5 Correct 7 ms 6748 KB Correct number of moves
6 Correct 6 ms 6744 KB Correct number of moves

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 7256 KB Output is correct
2 Correct 19 ms 7260 KB Output is correct
3 Correct 341 ms 30480 KB Output is correct
4 Correct 326 ms 33628 KB Output is correct
5 Correct 352 ms 35164 KB Output is correct

Subtask #5
14.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6492 KB Correct number of moves
2 Correct 17 ms 7256 KB Output is correct
3 Correct 19 ms 7260 KB Output is correct
4 Correct 19 ms 7260 KB Correct number of moves
5 Correct 7 ms 6748 KB Correct number of moves
6 Correct 6 ms 6744 KB Correct number of moves
7 Correct 341 ms 30480 KB Output is correct
8 Correct 326 ms 33628 KB Output is correct
9 Correct 352 ms 35164 KB Output is correct
10 Correct 349 ms 29008 KB Correct number of moves
11 Correct 321 ms 27216 KB Correct number of moves
12 Correct 392 ms 34800 KB Correct number of moves
13 Correct 363 ms 35468 KB Correct number of moves
14 Correct 375 ms 34164 KB Correct number of moves