Submission #66063278

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 <inttypes.h>
int N, M;
int A[312345], B[312345];
int counts[1123456];
int main(void) {
  int i;
  uint64_t ans = 0;
  if (scanf("%d%d", &N, &M) != 2) return 1;
  for (i = 0; i < M; i++) {
    if (scanf("%d%d", &A[i], &B[i]) != 2) return 1;
    if (A[i] - 1 <= N + 1 - B[i]) {
      counts[B[i] + (A[i] - 1)]++;
    } else {
      counts[A[i] - (N + 1 - B[i])]++;
    }
  }
  counts[1] += counts[N + 1];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <inttypes.h>

int N, M;
int A[312345], B[312345];

int counts[1123456];

int main(void) {
	int i;
	uint64_t ans = 0;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < M; i++) {
		if (scanf("%d%d", &A[i], &B[i]) != 2) return 1;
		if (A[i] - 1 <= N + 1 - B[i]) {
			counts[B[i] + (A[i] - 1)]++;
		} else {
			counts[A[i] - (N + 1 - B[i])]++;
		}
	}
	counts[1] += counts[N + 1];
	for (i = 1; i <= N; i++) {
		if (counts[i] > 0) ans += (uint64_t)counts[i] * (M - counts[i]);
	}
	printf("%" PRIu64 "\n", ans / 2);
	return 0;
}

/*

対応する向きに隣の点に同じ数だけ移動 → 並行

点1を通るように正規化する → 反対側の点の番号が向きに対応する

*/

Submission Info

Judge Result