Submission #869840

#	Time	Username	Problem	Language	Result	Execution time	Memory
869840		rainboy	Cat (info1cup19_cat)	C11	100 / 100	355 ms	20824 KiB

cat

#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 (stderr)

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 / 15
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15
• Subtask 5: 35 / 35