Problem:


Score : 1000 points

Problem Statement

Red bold fonts show the difference from C1.

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

Initially, only the lamp at (X, Y) 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 and Y.

Constraints

1 \leq N \leq 10^4

-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 and Y.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print X and Y, separated by a space.

Sample Input 1

4
-2 1
-2 2
0 1
1 0

Sample Output 1

-1 0

The following picture shows one possible sequence of operations:



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


Sample output:
-1 0

Submission status: Wrong Answer

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)
for y, xs in lights.items():
    if xs:
        print(xs.pop())
        break

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

    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), 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 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], start[1], 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], start[1], 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], start[1], 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], start[1], flush=True)


if __name__ == '__main__':
  main()