Submission #24475244

Source Code Expand

import sys
from collections import defaultdict, deque

def main(f):
  N = int(f.readline())
  A = [None] + list(map(int, f.readline().split()))

  link = [[] for i in range(2*10**5+1)]
  nodes = set()

  pair_flag = {}
  for i in range(1, N // 2 + 1):
    x, y = min(A[i], A[N+1-i]), max(A[i], A[N+1-i])
    if x == y:
      continue
    if (x, y) in pair_flag.keys():
      continue
    pair_flag[(x, y)] = True

    if y not in link[x]:
      link[x].append(y)
      link[y].append(x)
    nodes.add(x)
    nodes.add(y)

  result = 0
  flag = [0] * (2*10**5+1)
  for n in nodes:
    if flag[n] == 1:
      continue
    q = deque()
    q.append(n)
    nums = set()
    while q:
      x = q.pop()
      if flag[x] == 1:
        continue
      flag[x] = 1
      nums.add(x)
      for y in link[x]:
        if flag[y] == 0:
          q.append(y)
    result += len(nums) - 1

  print(result)

main(sys.stdin)

Submission Info

Submission Time
Task D - KAIBUNsyo
User enakai
Language PyPy3 (7.3.0)
Score 400
Code Size 950 Byte
Status AC
Exec Time 866 ms
Memory 167636 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 3
AC × 31
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt
Case Name Status Exec Time Memory
sample_01.txt AC 347 ms 111016 KiB
sample_02.txt AC 78 ms 92352 KiB
sample_03.txt AC 75 ms 92572 KiB
test_01.txt AC 81 ms 92356 KiB
test_02.txt AC 76 ms 92264 KiB
test_03.txt AC 79 ms 92412 KiB
test_04.txt AC 81 ms 92164 KiB
test_05.txt AC 77 ms 92320 KiB
test_06.txt AC 79 ms 92132 KiB
test_07.txt AC 256 ms 147728 KiB
test_08.txt AC 239 ms 144084 KiB
test_09.txt AC 122 ms 98320 KiB
test_10.txt AC 247 ms 138860 KiB
test_11.txt AC 146 ms 105624 KiB
test_12.txt AC 95 ms 88176 KiB
test_13.txt AC 175 ms 111184 KiB
test_14.txt AC 197 ms 113516 KiB
test_15.txt AC 197 ms 127108 KiB
test_16.txt AC 274 ms 142336 KiB
test_17.txt AC 204 ms 129080 KiB
test_18.txt AC 205 ms 128268 KiB
test_19.txt AC 274 ms 142196 KiB
test_20.txt AC 268 ms 142612 KiB
test_21.txt AC 270 ms 140508 KiB
test_22.txt AC 275 ms 142356 KiB
test_23.txt AC 222 ms 167636 KiB
test_24.txt AC 181 ms 149540 KiB
test_25.txt AC 109 ms 107856 KiB
test_26.txt AC 112 ms 107576 KiB
test_27.txt AC 866 ms 142932 KiB
test_28.txt AC 715 ms 143092 KiB