Problem:


Score : 1000 points

Problem Statement

There is an infinitely large triangular grid, as shown below.
Each point with integer coordinates contains a lamp.

Initially, only the lamp at (X, 0) was on, and all other lamps were off.
Then, Snuke performed the following operation zero or more times:

Choose two integers x and y.
Toggle (on to off, off to on) the following three lamps: (x, y), (x, y+1), (x+1, y).

After the operations, N lamps (x_1, y_1), \cdots, (x_N, y_N) are on, and all other lamps are off.
Find X.

Constraints

1 \leq N \leq 10^5

-10^{17} \leq x_i, y_i \leq 10^{17}

(x_i, y_i) are pairwise distinct.

The input is consistent with the statement, and you can uniquely determine X.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print X.

Sample Input 1

4
-2 1
-2 2
0 1
1 0

Sample Output 1

-1

The following picture shows one possible sequence of operations:



Sample input:
4
-2 1
-2 2
0 1
1 0


Sample output:
-1

Submission status: Wrong Answer

Solution code:
X=list()
Y=list()
N=int(input())
for i in range(N):
  x,y=map(int,input().split())
  X.append(x)
  Y.append(y)
print(abs(sum(X))-abs(sum(Y)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
from heapq import heapify, heappop, heappush


def move(lights):
    new_lights = defaultdict(set)
    for y, xs in lights.items():
        for x in xs:
            new_lights[-(x + y)].add(y)
    lights = new_lights
    ys = list(lights.keys())
    heapify(ys)
    prev_y = None
    while ys:
        y = heappop(ys)
        if y == prev_y:
            continue
        xs = sorted(lights[y])
        for l, r in zip(xs[::2], xs[1::2]):
            f = l
            while f < r:
                d = 1
                while f + d <= r:
                    d <<= 1
                d >>= 1
                ny = y + d
                lights[ny].symmetric_difference_update({f})
                heappush(ys, ny)
                f += d
            lights[y].difference_update({l, r})
        prev_y = y
    return lights


n = int(input())
xys = [tuple(map(int, line.split())) for line in sys.stdin]
lights = defaultdict(set)
for x, y in xys:
    lights[y].add(x)

lights = move(lights)
lights = move(lights)
lights = move(lights)
print(lights[0].pop())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools
import copy


def is_pair(a, b):
  d = abs(a - b)
  x = 1

  while x <= d:
    if x == d:
      return True

    x *= 2

  return False


def search(coods):
  while len(coods) > 1:
    triangle = None

    for x, y  in coods:
      if (x + 1, y) in coods and (x, y + 1) in coods:
        triangle = (x, y)
        break

    if triangle is not None:
      coods.remove((x, y))
      coods.remove((x + 1, y))
      coods.remove((x, y + 1))
      continue

    xc, yc = zip(*coods)
    xc = sum(xc) / len(xc)
    yc = sum(yc) / len(yc)

    pairs = set()
    targets = {c: 0 for c in coods}

    for (x1, y1), (x2, y2) in itertools.combinations(coods, 2):
      x3, y3 = None, None

      if is_pair(x1, x2) and y1 == y2:
        x3 = min(x1, x2)
        y3 = y1 + abs(x1 - x2)
      elif x1 == x2 and is_pair(y1, y2):
        x3 = x1 + abs(y1 - y2)
        y3 = min(y1, y2)
      elif is_pair(x1, x2) and abs(x1 - x2) == abs(y1 - y2):
        x3 = min(x1, x2)
        y3 = min(y1, y2)

      if x3 is not None and (x3, y3) not in coods:
        pairs.add(((x1, y1), (x2, y2), (x3, y3), abs(xc - x3) + abs(yc - y3), max(abs(x1 - x2), abs(y1 - y2))))
        targets[(x1, y1)] += 1
        targets[(x2, y2)] += 1

    if len(pairs) == 0:
      return None

    pairs = [(p1, p2, p3, c, d, min(targets[p1], targets[p2])) for p1, p2, p3, c, d in pairs]
    pairs.sort(key=lambda x: (x[5], x[3], x[4]))

    if pairs[0][5] == 1:
      p1, p2, p3, _, _, _ = pairs[0]
      coods.remove(p1)
      coods.remove(p2)
      coods.add(p3)
      continue

    for p1, p2, p3, _, _, _ in pairs:
      clone = copy.copy(coods)
      clone.remove(p1)
      clone.remove(p2)
      clone.add(p3)

      start = search(clone)

      if start is not None:
        return start

    return None

  return list(coods)[0]


def main():
  n = int(input())
  coods = set([tuple(map(int, input().split())) for _ in range(n)])
  start = search(coods)

  print(start[0], flush=True)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools
import copy


def is_pair(a, b):
  d = abs(a - b)
  x = 1

  while x <= d:
    if x == d:
      return True

    x *= 2

  return False


def search(coods):
  while len(coods) > 1:
    xc, yc = zip(*coods)
    xc = sum(xc) / len(xc)
    yc = sum(yc) / len(yc)

    pairs = set()
    targets = {c: 0 for c in coods}

    for (x1, y1), (x2, y2) in itertools.combinations(coods, 2):
      x3, y3 = None, None

      if is_pair(x1, x2) and y1 == y2:
        x3 = min(x1, x2)
        y3 = y1 + abs(x1 - x2)
      elif x1 == x2 and is_pair(y1, y2):
        x3 = x1 + abs(y1 - y2)
        y3 = min(y1, y2)
      elif is_pair(x1, x2) and abs(x1 - x2) == abs(y1 - y2):
        x3 = min(x1, x2)
        y3 = min(y1, y2)

      if x3 is not None and (x3, y3) not in coods:
        pairs.add(((x1, y1), (x2, y2), (x3, y3), abs(xc - x3) + abs(yc - y3), max(abs(x1 - x2), abs(y1 - y2))))
        targets[(x1, y1)] += 1
        targets[(x2, y2)] += 1

    if len(pairs) == 0:
      return None

    pairs = [(p1, p2, p3, c, d, min(targets[p1], targets[p2])) for p1, p2, p3, c, d in pairs]
    pairs.sort(key=lambda x: (x[5], x[3], x[4]))

    if pairs[0][4] == 1:
      p1, p2, p3, _, _, _ = pairs[0]
      coods.remove(p1)
      coods.remove(p2)
      coods.add(p3)
      continue

    for p1, p2, p3, _, _, _ in pairs:
      clone = copy.copy(coods)
      clone.remove(p1)
      clone.remove(p2)
      clone.add(p3)

      start = search(clone)

      if start is not None:
        return start

    return None

  return list(coods)[0]


def main():
  n = int(input())
  coods = set([tuple(map(int, input().split())) for _ in range(n)])
  start = search(coods)

  print(start[0], flush=True)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools
import copy


def is_pair(a, b):
  d = abs(a - b)
  x = 1

  while x <= d:
    if x == d:
      return True

    x *= 2

  return False


def search(coods):
  while len(coods) > 1:
    xc, yc = zip(*coods)
    xc = sum(xc) / len(xc)
    yc = sum(yc) / len(yc)

    pairs = set()
    targets = {c: 0 for c in coods}

    for (x1, y1), (x2, y2) in itertools.combinations(coods, 2):
      x3, y3 = None, None

      if is_pair(x1, x2) and y1 == y2:
        x3 = min(x1, x2)
        y3 = y1 + abs(x1 - x2)
      elif x1 == x2 and is_pair(y1, y2):
        x3 = x1 + abs(y1 - y2)
        y3 = min(y1, y2)
      elif is_pair(x1, x2) and abs(x1 - x2) == abs(y1 - y2):
        x3 = min(x1, x2)
        y3 = min(y1, y2)

      if x3 is not None:
        pairs.add(((x1, y1), (x2, y2), (x3, y3), abs(xc - x3) + abs(yc - y3), max(abs(x1 - x2), abs(y1 - y2))))
        targets[(x1, y1)] += 1
        targets[(x2, y2)] += 1

    if len(pairs) == 0:
      return None

    pairs = [(p1, p2, p3, c, d, min(targets[p1], targets[p2])) for p1, p2, p3, c, d in pairs]
    pairs.sort(key=lambda x: (x[5], x[3], x[4]))

    if pairs[0][4] == 1:
      p1, p2, p3, _, _, _ = pairs[0]
      coods.remove(p1)
      coods.remove(p2)
      coods.add(p3)
      continue

    for p1, p2, p3, _, _, _ in pairs:
      clone = copy.copy(coods)
      clone.remove(p1)
      clone.remove(p2)
      clone.add(p3)

      start = search(clone)

      if start is not None:
        return start

    return None

  return list(coods)[0]


def main():
  n = int(input())
  coods = set([tuple(map(int, input().split())) for _ in range(n)])
  start = search(coods)

  print(start[0], flush=True)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools
import copy


def is_pair(a, b):
  d = abs(a - b)
  x = 1

  while x <= d:
    if x == d:
      return True

    x *= 2

  return False


def search(coods):
  while len(coods) > 1:
    xc, yc = zip(*coods)
    xc = sum(xc) / len(xc)
    yc = sum(yc) / len(yc)

    pairs = set()
    targets = {c: 0 for c in coods}

    for (x1, y1), (x2, y2) in itertools.combinations(coods, 2):
      x3, y3 = None, None

      if is_pair(x1, x2) and y1 == y2:
        x3 = min(x1, x2)
        y3 = y1 + abs(x1 - x2)
      elif x1 == x2 and is_pair(y1, y2):
        x3 = x1 + abs(y1 - y2)
        y3 = min(y1, y2)
      elif is_pair(x1, x2) and abs(x1 - x2) == abs(y1 - y2):
        x3 = min(x1, x2)
        y3 = min(y1, y2)

      if x3 is not None:
        pairs.add(((x1, y1), (x2, y2), (x3, y3), abs(xc - x3) + abs(yc - y3), max(abs(x1 - x2), abs(y1 - y2))))
        targets[(x1, y1)] += 1
        targets[(x2, y2)] += 1

    if len(pairs) == 0:
      return None

    pairs = [(p1, p2, p3, c, d, min(targets[p1], targets[p2])) for p1, p2, p3, c, d in pairs]
    pairs.sort(key=lambda x: (x[5], x[3], x[4]))

    if pairs[0][4] == 1:
      p1, p2, p3, _, _, _ = pairs[0]
      coods.remove(p1)
      coods.remove(p2)
      coods.add(p3)
      continue

    for p1, p2, p3, _, _, _ in pairs:
      clone = copy.copy(coods)
      clone.remove(p1)
      clone.remove(p2)
      clone.add(p3)

      start = search(clone)

      if start is not None:
        return start

  return list(coods)[0]


def main():
  n = int(input())
  coods = set([tuple(map(int, input().split())) for _ in range(n)])
  start = search(coods)

  print(start[0], flush=True)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools
import copy


def is_pair(a, b):
  d = abs(a - b)
  x = 1

  while x <= d:
    if x == d:
      return True

    x *= 2

  return False


def search(coods):
  while len(coods) > 1:
    pairs = set()
    targets = {c: 0 for c in coods}

    for (x1, y1), (x2, y2) in itertools.combinations(coods, 2):
      x3, y3 = None, None

      if is_pair(x1, x2) and y1 == y2:
        x3 = min(x1, x2)
        y3 = y1 + abs(x1 - x2)
      elif x1 == x2 and is_pair(y1, y2):
        x3 = x1 + abs(y1 - y2)
        y3 = min(y1, y2)
      elif is_pair(x1, x2) and abs(x1 - x2) == abs(y1 - y2):
        x3 = min(x1, x2)
        y3 = min(y1, y2)

      if x3 is not None:
        pairs.add(((x1, y1), (x2, y2), (x3, y3), max(abs(x1 - x2), abs(y1 - y2))))
        targets[(x1, y1)] += 1
        targets[(x2, y2)] += 1

    if len(pairs) == 0:
      return None

    pairs = [(p1, p2, p3, d, min(targets[p1], targets[p2])) for p1, p2, p3, d in pairs]
    pairs.sort(key=lambda x: (x[4], x[3]))

    if pairs[0][4] == 1:
      p1, p2, p3, _, _ = pairs[0]
      coods.remove(p1)
      coods.remove(p2)
      coods.add(p3)
      continue

    for p1, p2, p3, _, _ in pairs:
      clone = copy.copy(coods)
      clone.remove(p1)
      clone.remove(p2)
      clone.add(p3)

      start = search(clone)

      if start is not None:
        return start

  return list(coods)[0]


def main():
  n = int(input())
  coods = set([tuple(map(int, input().split())) for _ in range(n)])
  start = search(coods)

  print(start[0], flush=True)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import itertools
import copy


def is_pair(a, b):
  d = abs(a - b)
  x = 1

  while x <= d:
    if x == d:
      return True

    x *= 2

  return False


def search(coods):
  while len(coods) > 1:
    pairs = {c: [] for c in coods}

    for (x1, y1), (x2, y2) in itertools.combinations(coods, 2):
      x3, y3 = None, None

      if is_pair(x1, x2) and y1 == y2:
        x3 = min(x1, x2)
        y3 = y1 + abs(x1 - x2)
      elif x1 == x2 and is_pair(y1, y2):
        x3 = x1 + abs(y1 - y2)
        y3 = min(y1, y2)
      elif is_pair(x1, x2) and abs(x1 - x2) == abs(y1 - y2):
        x3 = min(x1, x2)
        y3 = min(y1, y2)

      if x3 is not None:
        pairs[(x1, y1)].append(((x1, y1), (x2, y2), (x3, y3)))
        pairs[(x2, y2)].append(((x1, y1), (x2, y2), (x3, y3)))

    if len(pairs) == 0:
      return None

    pairs = [p for p in pairs.values() if len(p) != 0]
    pairs.sort(key=lambda x: len(x))
    pair = pairs[0]

    if len(pair) == 1:
      p1, p2, p3 = pair[0]
      coods.remove(p1)
      coods.remove(p2)
      coods.add(p3)
      continue

    for p1, p2, p3 in pair:
      clone = copy.copy(coods)
      print('--', p1, p2, p3)
      clone.remove(p1)
      clone.remove(p2)
      clone.add(p3)

      start = search(clone)

      if start is not None:
        return start

  return list(coods)[0]


def main():
  n = int(input())
  coods = set([tuple(map(int, input().split())) for _ in range(n)])
  start = search(coods)

  print(start[0], flush=True)


if __name__ == '__main__':
  main()

Submission status: Runtime Error

Solution code:
N=int(input())
for i in range(N):
  x,y=map(int,input().split())
  X.append(x)
  Y.append(y)
print(abs(sum(X))-abs(sum(Y)))

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from heapq import heapify, heappop, heappush


def up(lights, y, l, r, ys):
    ny = y + r - l
    if l in lights[ny]:
        lights[ny].remove(l)
    else:
        lights[ny].add(l)
    heappush(ys, ny)


def move(lights):
    new_lights = defaultdict(set)
    for y, xs in lights.items():
        for x in xs:
            new_lights[-(x + y)].add(y)
    lights = new_lights
    ys = list(lights.keys())
    heapify(ys)
    prev_y = None
    while ys:
        y = heappop(ys)
        if y == prev_y:
            continue
        xs = sorted(lights[y])
        for l, r in zip(xs[::2], xs[1::2]):
            f = l
            while f < r:
                d = 1
                while f + d <= r:
                    d <<= 1
                d >>= 1
                up(lights, y, f, f + d, ys)
                f += d + 1
            lights[y].difference_update({l, r})
        prev_y = y
    return lights


n = int(input())
xys = [tuple(map(int, line.split())) for line in sys.stdin]
lights = defaultdict(set)
for x, y in xys:
    lights[y].add(x)

lights = move(lights)
lights = move(lights)
lights = move(lights)
print(lights[0].pop())