Problem:


Score : 800 points

Problem Statement

Takahashi is doing a research on sets of points in a plane.
Takahashi thinks a set S of points in a coordinate plane is a good set when S satisfies both of the following conditions:

The distance between any two points in S is not \sqrt{D_1}.

The distance between any two points in S is not \sqrt{D_2}.

Here, D_1 and D_2 are positive integer constants that Takahashi specified.

Let X be a set of points (i,j) on a coordinate plane where i and j are integers and satisfy 0 ≤ i,j < 2N.

Takahashi has proved that, for any choice of D_1 and D_2, there exists a way to choose N^2 points from X so that the chosen points form a good set.
However, he does not know the specific way to choose such points to form a good set.
Find a subset of X whose size is N^2 that forms a good set.

Constraints

1 ≤ N ≤ 300

1 ≤ D_1 ≤ 2×10^5

1 ≤ D_2 ≤ 2×10^5

All values in the input are integers.

Input

Input is given from Standard Input in the following format:

N D_1 D_2

Output

Print N^2 distinct points that satisfy the condition in the following format:

x_1 y_1
x_2 y_2
:
x_{N^2} y_{N^2}

Here, (x_i,y_i) represents the i-th chosen point.
0 ≤ x_i,y_i < 2N must hold, and they must be integers.
The chosen points may be printed in any order.
In case there are multiple possible solutions, you can output any.

Sample Input 1

2 1 2

Sample Output 1

0 0
0 2
2 0
2 2

Among these points, the distance between 2 points is either 2 or 2\sqrt{2}, thus it satisfies the condition.

Sample Input 2

3 1 5

Sample Output 2

0 0
0 2
0 4
1 1
1 3
1 5
2 0
2 2
2 4



Sample input:
2 1 2


Sample output:
0 0
0 2
2 0
2 2

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def isqrt(n):
    """integer sqrt: the maximum integer less than or equal to sqrt(n)"""
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def solve(f):
    n, d1, d2 = f.read_int_list()

    a = [[0] * (2*n) for _ in range(2*n)]
    d = [d1, d2]

    for i in range(2):
        g = [[[] for _ in range(2*n)] for _ in range(2*n)]
        for dx in range(2*n):
            dy2 = d[i] - dx**2
            if dy2 < 0: continue
            dy = isqrt(dy2)
            if dy**2 != dy2: continue

            for x in range(2*n):
                for y in range(2*n):
                    for sgn in [1, -1]:
                        if dx*dy == 0 and sgn == -1: continue
                        if 0 <= x+dx < 2*n and 0 <= y+sgn*dy < 2*n:
                            g[x][y].append((x+dx, y+sgn*dy))
                            g[x+dx][y+sgn*dy].append((x, y))

        vis = [[False] * (2*n) for _ in range(2*n)]
        for x in range(2*n):
            for y in range(2*n):
                if not vis[x][y]:
                    c = 2**i
                    que = [(x, y)]
                    while len(que) > 0:
                        que2 = []
                        for xi, yi in que:
                            if vis[xi][yi]: continue
                            vis[xi][yi] = True
                            a[xi][yi] += c
                            que2.extend(g[xi][yi])
                        que = que2
                        c *= -1

    cnt = collections.defaultdict(list)
    for x in range(2*n):
        for y in range(2*n):
            cnt[a[x][y]].append((x, y))

    for k, v in cnt.items():
        if len(v) >= n**2:
            return "\n".join(["%d %d"%item for item in v[:n**2]])


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return next(self.file).strip() if self.file else input()

    def next_case(self):
        next(self.file)
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print("Case #%d"%f.case)
            print(solve(f))
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print(solve(f))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def isqrt(n):
    """integer sqrt: the maximum integer less than or equal to sqrt(n)"""
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def solve(f):
    n, d1, d2 = f.read_int_list()

    a = [[0] * (2*n) for _ in xrange(2*n)]
    d = [d1, d2]

    for i in xrange(2):
        g = [[[] for _ in xrange(2*n)] for _ in xrange(2*n)]
        for dx in xrange(2*n):
            dy2 = d[i] - dx**2
            if dy2 < 0: continue
            dy = isqrt(dy2)
            if dy**2 != dy2: continue

            for x in xrange(2*n):
                for y in xrange(2*n):
                    for sgn in [1, -1]:
                        if dx*dy == 0 and sgn == -1: continue
                        if 0 <= x+dx < 2*n and 0 <= y+sgn*dy < 2*n:
                            g[x][y].append((x+dx, y+sgn*dy))
                            g[x+dx][y+sgn*dy].append((x, y))

        vis = [[False] * (2*n) for _ in xrange(2*n)]
        for x in xrange(2*n):
            for y in xrange(2*n):
                if not vis[x][y]:
                    c = 2**i
                    que = [(x, y)]
                    while len(que) > 0:
                        que2 = []
                        for xi, yi in que:
                            if vis[xi][yi]: continue
                            vis[xi][yi] = True
                            a[xi][yi] += c
                            que2.extend(g[xi][yi])
                        que = que2
                        c *= -1

    cnt = collections.defaultdict(list)
    for x in xrange(2*n):
        for y in xrange(2*n):
            cnt[a[x][y]].append((x, y))

    for k, v in cnt.items():
        if len(v) >= n**2:
            return "\n".join(["%d %d"%item for item in v[:n**2]])


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def isqrt(n):
    """integer sqrt: the maximum integer less than or equal to sqrt(n)"""
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def solve(f):
    n, d1, d2 = f.read_int_list()

    a = [[0] * (2*n) for _ in xrange(2*n)]
    g = [collections.defaultdict(list) for _ in xrange(2)]
    d = [d1, d2]

    for i in xrange(2):
        for dx in xrange(2*n):
            dy2 = d[i] - dx**2
            if dy2 < 0: continue
            dy = isqrt(dy2)
            if dy**2 != dy2: continue

            for x in xrange(2*n):
                for y in xrange(2*n):
                    for sgn in [1, -1]:
                        if dx*dy == 0 and sgn == -1: continue
                        if 0 <= x+dx < 2*n and 0 <= y+sgn*dy < 2*n:
                            g[i][(x, y)].append((x+dx, y+sgn*dy))
                            g[i][(x+dx, y+sgn*dy)].append((x, y))

        vis = [[False] * (2*n) for _ in xrange(2*n)]
        for x in xrange(2*n):
            for y in xrange(2*n):
                if not vis[x][y]:
                    c = 2**i
                    que = [(x, y)]
                    while len(que) > 0:
                        que2 = []
                        for v in que:
                            if vis[v[0]][v[1]]: continue
                            vis[v[0]][v[1]] = True
                            a[v[0]][v[1]] += c
                            que2.extend(g[i][v])
                        que = que2
                        c *= -1

    cnt = collections.defaultdict(list)
    for x in xrange(2*n):
        for y in xrange(2*n):
            cnt[a[x][y]].append((x, y))

    for k, v in cnt.items():
        if len(v) >= n**2:
            return "\n".join(["%d %d"%item for item in v[:n**2]])


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def isqrt(n):
    """integer sqrt: the maximum integer less than or equal to sqrt(n)"""
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def solve(f):
    n, d1, d2 = f.read_int_list()

    a = [[0] * (2*n) for _ in xrange(2*n)]
    g = [collections.defaultdict(list) for _ in xrange(2)]
    d = [d1, d2]

    for i in xrange(2):
        for x1 in xrange(2*n):
            for x2 in xrange(x1, 2*n):
                dy2 = d[i] - (x1-x2) ** 2
                if dy2 >= 0:
                    dy = isqrt(dy2)
                    if dy**2 != dy2: continue
                    for y1 in xrange(2*n):
                        for sgn in [1, -1]:
                            if dy == 0 and sgn == -1: continue
                            y2 = y1 + sgn*dy
                            if not 0 <= y2 < 2*n: continue
                            if x1 == x2 and y1 < y2: continue
                            g[i][(x1, y1)].append((x2, y2))
                            g[i][(x2, y2)].append((x1, y1))

        vis = [[False] * (2*n) for _ in xrange(2*n)]
        for x in xrange(2*n):
            for y in xrange(2*n):
                if not vis[x][y]:
                    c = 2**i
                    que = [(x, y)]
                    while len(que) > 0:
                        que2 = []
                        for v in que:
                            if vis[v[0]][v[1]]: continue
                            vis[v[0]][v[1]] = True
                            a[v[0]][v[1]] += c
                            que2 += g[i][v]
                        que = que2
                        c *= -1

    cnt = collections.defaultdict(list)
    for x in xrange(2*n):
        for y in xrange(2*n):
            cnt[a[x][y]].append((x, y))

    for k, v in cnt.items():
        if len(v) >= n**2:
            return "\n".join(["%d %d"%item for item in v[:n**2]])


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def isqrt(n):
    """integer sqrt: the maximum integer less than or equal to sqrt(n)"""
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def solve(f):
    n, d1, d2 = f.read_int_list()

    a = [[0] * (2*n) for _ in xrange(2*n)]
    g = [collections.defaultdict(list) for _ in xrange(2)]
    d = [d1, d2]

    for i in xrange(2):
        for x1 in xrange(2*n):
            for x2 in xrange(2*n):
                for y1 in xrange(2*n):
                    for y2 in xrange(2*n):
                        dd = (x1-x2)**2 + (y1-y2)**2
                        if dd == d[i]: g[i][(x1, y1)].append((x2, y2))

        vis = [[False] * (2*n) for _ in xrange(2*n)]
        for x in xrange(2*n):
            for y in xrange(2*n):
                if not vis[x][y]:
                    c = 2**i
                    que = [(x, y)]
                    while len(que) > 0:
                        que2 = []
                        for v in que:
                            if vis[v[0]][v[1]]: continue
                            vis[v[0]][v[1]] = True
                            a[v[0]][v[1]] += c
                            que2 += g[i][v]
                        que = que2
                        c *= -1

    cnt = collections.defaultdict(list)
    for x in xrange(2*n):
        for y in xrange(2*n):
            cnt[a[x][y]].append((x, y))

    for k, v in cnt.items():
        if len(v) >= n**2:
            return "\n".join(["%d %d"%item for item in v[:n**2]])


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from itertools import product
from time import process_time as timer
 
import numpy as np

def helper(N,D):

  banned = set()
  for x in range(0, int(sqrt(D/2))+2):
    if D > x*x:
      y = sqrt(D-x*x)
      if y == int(y):
        y = int(y)
 
        for a,b in {(x,y),(y,x)}:
          for s,t in product((1,-1), repeat=2):
            banned.add((s*a,t*b))
  banned = list(banned)
  M = N*2
 
  grid = [[0 for _ in range(M)] for _ in range(M)]

  p0 = (0,0)
  stack = []
  while p0:

    stack.append(p0)
    grid[p0[0]][p0[1]] = 1

    while stack:
      x,y = stack.pop()
      t = grid[x][y]
      for dx,dy in banned:
        xx,yy = x+dx,y+dy
        if 0 <= xx < M and 0 <= yy < M and grid[xx][yy] == 0:
          grid[xx][yy] = -t
          stack.append((xx,yy))
    
    p0 = None
    for x in range(M):
      for y in range(M):
        if grid[x][y] == 0:
          p0 = (x,y)
          break
      if p0:
        break

  return np.array(grid)
 
N,D1,D2 = map(int,input().split())
M = N*2
g1 = helper(N,D1)
g2 = helper(N,D2)
 
if np.count_nonzero(g1==1)*2 > M*M:
  g1 = g1==1
else:
  g1 = g1==-1
 
if np.sum(g1*g2) > 0:
  ans = g1&(g2==1)
else:
  ans = g1&(g2==-1)
 
 
for x,y in np.transpose(np.nonzero(ans))[:N*N]:
  print(x,y)
 
# print(ans.astype(int))
# print(np.sum(ans), N*N)

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt
from itertools import product

import numpy as np

def helper(N,D):
  banned = list()
  for x in range(0, int(sqrt(D/2))+2):
    if D > x*x:
      y = sqrt(D-x*x)
      if y == int(y):
        y = int(y)

        for a,b in {(x,y),(y,x)}:
          for s,t in product((1,-1), repeat=2):
            banned.append((s*a,t*b))

  M = N*2

  grid = np.zeros((M,M), dtype=int)

  p0 = (0,0)
  while p0:
    stack = [p0]
    grid[stack[0]] = 1
    while stack:
      x,y = stack.pop()
      t = grid[x,y]
      for dx,dy in banned:
        xx,yy = x+dx,y+dy
        if 0 <= xx < M and 0 <= yy < M and grid[xx,yy] == 0:
          grid[xx,yy] = -t

    l = np.transpose(np.nonzero(grid==0))
    if l.size > 0:
      p0 = tuple(l[0])
    else:
      p0 = None


  return grid

N,D1,D2 = map(int,input().split())
M = N*2
g1 = helper(N,D1)
g2 = helper(N,D2)

if np.count_nonzero(g1==1)*2 > M*M:
  g1 = g1==1
else:
  g1 = g1==-1

if np.sum(g1*g2) > 0:
  ans = g1&(g2==1)
else:
  ans = g1&(g2==-1)


for x,y in np.transpose(np.nonzero(ans))[:N*N]:
  print(x,y)

Submission status: Time Limit Exceeded

Solution code:
import math
n,d1,d2=map(int,input().split())

tmp = int(math.sqrt(max(d1,d2)))
darr = []
for i in range(tmp+1):
  for j in range(i,tmp+1):
    if i*i + j*j == d1 or i*i + j*j == d2:
      darr.append([i,j])
      break
    elif max(d1,d2) < i*i +j*j:
      break
check = []
for k in range(2*n):
  for l in range(2*n):
    check.append([k,l])

count = 0
while count < n*n:
  tmp = check.pop(0)
  print(str(tmp[0])+' '+str(tmp[1]))
  for d in darr:
    if [tmp[0]+d[0],tmp[1]+d[1]] in check:
      check.remove([tmp[0]+d[0],tmp[1]+d[1]])
    if [tmp[0]+d[1],tmp[1]+d[0]] in check:
      check.remove([tmp[0]+d[1],tmp[1]+d[0]])
  count += 1

Submission status: Time Limit Exceeded

Solution code:
N, D1, D2 = [int(a) for a in input().split()]
import math

table = [
    [False for _ in range(N * 2)]
    for _ in range(N * 2)
]

xd1 = [
    (x, D1 - (x * x)) for x in range(int(math.ceil(math.sqrt(D1))) + 1)
]
xd1_ = [(x, y, int(math.sqrt(y))) for x, y in xd1 if y >= 0]
xd1 = [(x, yy) for x, y, yy in xd1_ if y == yy * yy]

xd2 = [
    (x, D2 - (x * x)) for x in range(int(math.ceil(math.sqrt(D2))) + 1)
]
xd2_ = [(x, y, int(math.sqrt(y))) for x, y in xd2 if y >= 0]
xd2 = [(x, yy) for x, y, yy in xd2_ if y == yy * yy]


def check(x, y):
    return 0 <= x < 2 * N and 0 <= y < 2 * N


def solve(skip):
    res = []

    for i in range(N * 2):
        for j in range(N * 2):
            if skip != 0:
                skip -= 1
                continue
            if table[i][j]:
                continue

            res.append((i, j))
            if len(res) == N * N:
                return res

            for x, y in xd1:
                p, q = x + i, y + j
                if check(p, q):
                    table[p][q] = True
                p, q = -x + i, y + j
                if check(p, q):
                    table[p][q] = True
                p, q = x + i, -y + j
                if check(p, q):
                    table[p][q] = True
                p, q = -x + i, -y + j
                if check(p, q):
                    table[p][q] = True
            for x, y in xd2:
                p, q = x + i, y + j
                if check(p, q):
                    table[p][q] = True
                p, q = -x + i, y + j
                if check(p, q):
                    table[p][q] = True
                p, q = x + i, -y + j
                if check(p, q):
                    table[p][q] = True
                p, q = -x + i, -y + j
                if check(p, q):
                    table[p][q] = True
    return None


for s in range(N * N):
    res = solve(s)
    if res is None:
        continue
    for x, y in res:
        print(x, y)
    break

Submission status: Time Limit Exceeded

Solution code:
from math import sqrt

N0,D1,D2 = map(int,input().split())
N = 2*N0
banned = set()
for d in [D1,D2]:
  for x in range(0, int(sqrt(d/2)+1)):
    y = sqrt(d-x*x)
    if y == int(y):
      y = int(y)
      banned.add((x,y))
      banned.add((y,x))

grid = [[True for _ in range(N*2)] for _ in range(N*2)]

points = []

for y in range(N0):
  g = grid[y]
  for x in range(N0):

    if g[x]:
      points.append((x,y))

      for dx,dy in banned:
        if x+dx < N0 and y+dy < N0:
          grid[y+dy][x+dx] = False

from time import sleep

if len(points) < N0**2:
  sleep(3)

for x,y in points[:N0**2]:
  print(x,y)

Submission status: Time Limit Exceeded

Solution code:
N,D_1,D_2 = map(int,input().split())

P = [[i,j] for i in range(2*N) for j in range(2*N)]
B=[]

for k in range(N**2):
    B = []
    o = P[0]
    P.remove(o)
    print(o[0], o[1])
    for p in P:
        if (p[0]-o[0])**2 + (p[1]-o[1])**2 == D_1:
            B.append(p)
        if (p[0]-o[0])**2 + (p[1]-o[1])**2 == D_2:
            B.append(p)
    for b in B:
        P.remove(b)

Submission status: Time Limit Exceeded

Solution code:
import math
n,d1,d2=map(int,input().split())

tmp = int(math.sqrt(max(d1,d2)))
darr = []
for i in range(tmp+1):
  for j in range(i,tmp+1):
    if i*i + j*j == d1 or i*i + j*j == d2:
      if [i,j] not in darr and [j,i] not in darr:
        darr.append([i,j])
result = []
check = []

for x in range(2*n):
  if len(result) == n*n:
    break
  for y in range(2*n):
    if len(result) == n*n:
      break
    if [x,y] not in check:
      result.append([x,y])
      for a in darr:
        if x+a[0] < 2*n and y+a[1] <= 2*n and [x+a[0],y+a[1]] not in check:
          check.append([x+a[0],y+a[1]])
        if x+a[1] < 2*n and y+a[0] < 2*n and [x+a[1],y+a[0]] not in check:
          check.append([x+a[1],y+a[0]])
for r in result:
  print(str(r[0])+' '+str(r[1]))

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,d1,d2 = LI()
    nn = n**2
    n2 = n*2
    r = []
    t = []
    for i in range(n*2):
        ii = i**2
        for j in range(i, n*2):
            jj = j**2
            if ii+jj == d1 or ii+jj == d2:
                t.append((i,j))
                t.append((i,-j))
                t.append((-i,j))
                t.append((-i,-j))
                if i != j:
                    t.append((j,i))
                    t.append((j,-i))
                    t.append((-j,i))
                    t.append((-j,-i))
    t = list(set(t))

    def tf(c):
        f = [[None] * (n*2) for _ in range(n*2)]
        r = []
        tt = []
        ttt = [[] for _ in range(c)]
        for i in range(n*2 // c + 1):
            for ii in range(i*c,min((i+1)+c,n*2)):
                ttt[ii%c].append(ii)
        for ti in ttt:
            tt += ti
        for i in tt:
            for j in tt:
                if not f[i][j] is None:
                    continue
                f[i][j] = 1
                r.append((i,j))
                if len(r) == nn:
                    break
                for di,dj in t:
                    ni = i + di
                    nj = j + dj
                    if 0 <= ni < n2 and 0 <= nj < n2:
                        f[ni][nj] = 1
            if len(r) == nn:
                break
        return r

    rc = 1
    r = tf(rc)
    while len(r) != nn:
        rc += 1
        r = tf(rc)

    return '\n'.join(map(lambda x: '{} {}'.format(x[0],x[1]), r))


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,d1,d2 = LI()
    nn = n**2
    n2 = n*2
    r = []
    t = []
    for i in range(n*2):
        ii = i**2
        for j in range(i, n*2):
            jj = j**2
            if ii+jj == d1 or ii+jj == d2:
                t.append((i,j))
                t.append((i,-j))
                t.append((-i,j))
                t.append((-i,-j))
                if i != j:
                    t.append((j,i))
                    t.append((j,-i))
                    t.append((-j,i))
                    t.append((-j,-i))
    t = list(set(t))

    def tf(c):
        f = [[None] * (n*2) for _ in range(n*2)]
        r = []
        tt = []
        ttt = [[] for _ in range(c)]
        for i in range(n*2 // c + 1):
            for ii in range(i*c,min((i+1)+c,n*2)):
                ttt[ii%c].append(ii)
        for ti in ttt:
            tt += ti
        for i in tt:
            for j in range(n*2):
                if not f[i][j] is None:
                    continue
                f[i][j] = 1
                r.append((i,j))
                if len(r) == nn:
                    break
                for di,dj in t:
                    ni = i + di
                    nj = j + dj
                    if 0 <= ni < n2 and 0 <= nj < n2:
                        f[ni][nj] = 1
            if len(r) == nn:
                break
        return r

    rc = 1
    r = tf(rc)
    while len(r) != nn:
        rc += 1
        r = tf(rc)

    return '\n'.join(map(lambda x: '{} {}'.format(x[0],x[1]), r))


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,d1,d2 = LI()
    nn = n**2
    n2 = n*2
    r = []
    t = []
    for i in range(n*2):
        ii = i**2
        for j in range(i, n*2):
            jj = j**2
            if ii+jj == d1 or ii+jj == d2:
                t.append((i,j))
                t.append((i,-j))
                t.append((-i,j))
                t.append((-i,-j))
                if i != j:
                    t.append((j,i))
                    t.append((j,-i))
                    t.append((-j,i))
                    t.append((-j,-i))
    t = list(set(t))

    def tf(c):
        f = [[None] * (n*2) for _ in range(n*2)]
        r = []
        tt = []
        ttt = [[] for _ in range(c)]
        for i in range(n*2 // c + 1):
            for ii in range(i*c,min((i+1)+c,n*2)):
                ttt[ii%c].append(i)
        for ti in ttt:
            tt += ti
        for i in tt:
            for j in range(n*2):
                if not f[i][j] is None:
                    continue
                f[i][j] = 1
                r.append((i,j))
                if len(r) == nn:
                    break
                for di,dj in t:
                    ni = i + di
                    nj = j + dj
                    if 0 <= ni < n2 and 0 <= nj < n2:
                        f[ni][nj] = 1
            if len(r) == nn:
                break
        return r

    rc = 1
    r = tf(rc)
    while len(r) != nn:
        rc += 1
        r = tf(rc)

    return '\n'.join(map(lambda x: '{} {}'.format(x[0],x[1]), r))


print(main())