https://train.usaco.org/usacoprob2?a=Dz2NOQGuhll&S=ariprog thats the description for the problem I feel like i've optimized my program to the max It has to be able to run N = 25 M = 250 in under 5 seconds ;-;
Code here: """ /* ID: your_id_here LANG: PYTHON3 TASK: ariprog */ """ import time curr = time.time() with open("ariprog.in") as a: n = int(a.readline()) m = int(a.readline()) s = set([]) for p in range(m+1): for q in range(m+1): s.add((p*p)+(q*q)) ma = m*m*2 def calc(st): mb = (ma - st)//(n-1) out = [] for j in range(1, mb+1): l = True for i in range(1, n): if not i*j+st in s: l = False break if l: out.append([st, j]) return out tot = [] for i in s: tot = tot+calc(i) if len(tot): def partition(array, low, high, b): pivot = array[high][b] i = low - 1 for j in range(low, high): if array[j][b] <= pivot: i = i + 1 (array[i], array[j]) = (array[j], array[i]) (array[i + 1], array[high]) = (array[high], array[i + 1]) return i + 1 def quickSort(array, low, high, b): if low < high: pi = partition(array, low, high, b) quickSort(array, low, pi - 1, b) quickSort(array, pi + 1, high, b) quickSort(tot, 0, len(tot)-1, 1) prev = tot[0][1] s = 0 #print(tot) for i in range(len(tot)): if tot[i][1] != prev: prev = tot[i][1] #print(s, i) quickSort(tot, s, i-1, 0) #print(tot) s = i with open("ariprog.out", "w") as a: for i in range(len(tot)): a.write(str(tot[i][0]) + " " + str(tot[i][1]) + "\n") else: with open("ariprog.out", "w") as a: a.write("NONE\n") print(time.time()-curr)