Submission #64847065

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
struct pair_s {
  int a, b;
  int idx;
};
int cmp(const void* x, const void* y) {
  struct pair_s a = *(const struct pair_s*)x, b = *(const struct pair_s*)y;
  if (a.a != b.a) return a.a < b.a ? -1 : 1;
  if (a.b != b.b) return a.b < b.b ? -1 : 1;
  return a.idx < b.idx ? -1 : a.idx > b.idx;
}
int A[212345 * 2];
struct pair_s pairs[212345 * 2];
int ng[212345];
int main(void) {
  int T, tc;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

struct pair_s {
	int a, b;
	int idx;
};

int cmp(const void* x, const void* y) {
	struct pair_s a = *(const struct pair_s*)x, b = *(const struct pair_s*)y;
	if (a.a != b.a) return a.a < b.a ? -1 : 1;
	if (a.b != b.b) return a.b < b.b ? -1 : 1;
	return a.idx < b.idx ? -1 : a.idx > b.idx;
}

int A[212345 * 2];
struct pair_s pairs[212345 * 2];
int ng[212345];

int main(void) {
	int T, tc;
	if (scanf("%d", &T) != 1) return 1;
	for (tc = 1; tc <= T; tc++) {
		int N;
		int i;
		int ans = 0;
		if (scanf("%d", &N) != 1) return 1;
		for (i = 0; i < 2 * N; i++) {
			if (scanf("%d", &A[i]) != 1) return 1;
		}
		for (i = 1; i < 2 * N; i++) {
			if (A[i - 1] <= A[i]) {
				pairs[i - 1].a = A[i - 1];
				pairs[i - 1].b = A[i];
			} else {
				pairs[i - 1].a = A[i];
				pairs[i - 1].b = A[i - 1];
			}
			pairs[i - 1].idx = i - 1;
			if (A[i - 1] == A[i]) ng[A[i]] = tc;
		}
		qsort(pairs, 2 * N - 1, sizeof(*pairs), cmp);
		for (i = 1; i < 2 * N - 1; i++) {
			if (
				ng[pairs[i].a] != tc &&
				ng[pairs[i].b] != tc &&
				pairs[i - 1].a == pairs[i].a &&
				pairs[i - 1].b == pairs[i].b &&
				(
					pairs[i - 1].idx < pairs[i].idx - 1 ||
					(
						i > 1 &&
						pairs[i - 2].a == pairs[i].a &&
						pairs[i - 2].b == pairs[i].b &&
						pairs[i - 2].idx < pairs[i].idx - 1
					)
				)
			) {
				ans++;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

/*

隣接している数値はアウト
それ以外で、隣同士で順不同 (すなわち、小さい方を先に正規化) のペアを取り出して、
同じペアが2個あればおｋ
↑嘘 2 1 2 x x x x x 1 みたいなので死ぬ

「ソートして隣接した要素の位置が2以上離れていればおｋ」だと、1 2 1 2 みたいなやつで死ぬ
なぜなら、同じペアが3個検出され、1ずつしか離れていないことになる

隣接している数値は1ペアしか出てこないので、特別扱いで弾かなくておｋ
↑大嘘 2 1 1 2 みたいなやつで引っかかる
↑大嘘ってほどでもない ペアから外す必要はない 別のフラグで管理する

*/

Submission Info

Judge Result