def main(): from sys import stdin, setrecursionlimit # setrecursionlimit(1000000) input = stdin.readline def iinput(): return int(input()) def sinput(): return input().rstrip() def i0input(): return int(input()) - 1 def linput(): return list(input().split()) def liinput(): return list(map(int, input().split())) def miinput(): return map(int, input().split()) def li0input(): return list(map(lambda x: int(x) - 1, input().split())) def mi0input(): return map(lambda x: int(x) - 1, input().split()) INF = 1000000000000000000 MOD = 1000000007 from itertools import combinations from math import sqrt, exp def score(): X = [[] for _ in [0] * K] Y = [[] for _ in [0] * K] for b, m, e in zip(Bs, Ms, Es): start = 2 * b diff = 2 * e end = 2 * m last = (b - m) // e thr = start * (last + 1) - last * (last + 1) // 2 * diff for i, t in enumerate(T): if t <= thr: ok = MAXBE ng = -1 while ng + 1 < ok: ch = (ng + ok) // 2 if t < start * (ch + 1) - ch * (ch + 1) // 2 * diff: ng = ch else: ok = ch t -= start * ok - ok * (ok - 1) // 2 * diff if ok % 2: sgn = -1 else: sgn = 1 if t <= (start - ok * diff) // 2: X[i].append(sgn * t) else: X[i].append(sgn * (start - ok * diff - t)) else: t -= start * (last + 1) - last * (last + 1) // 2 * diff ok = last + t // end t %= end if ok % 2: sgn = -1 else: sgn = 1 if t <= end // 2: X[i].append(sgn * t) else: X[i].append(sgn * (end - t)) for i, t in enumerate(U): if t <= thr: ok = MAXBE ng = -1 while ng + 1 < ok: ch = (ng + ok) // 2 if t < start * (ch + 1) - ch * (ch + 1) // 2 * diff: ng = ch else: ok = ch t -= start * ok - ok * (ok - 1) // 2 * diff if ok % 2: sgn = -1 else: sgn = 1 if t <= (start - ok * diff) // 2: Y[i].append(sgn * t) else: Y[i].append(sgn * (start - ok * diff - t)) else: t -= start * (last + 1) - last * (last + 1) // 2 * diff ok = last + t // end t %= end if ok % 2: sgn = -1 else: sgn = 1 if t <= end // 2: Y[i].append(sgn * t) else: Y[i].append(sgn * (end - t)) tmp1 = [] for x in X: tmp1.append(0) for i in range(N): for j in range(i+1, N): tmp1[-1] += abs(x[i] - x[j]) / (Bs[i] + Bs[j]) tmp1[-1] *= 20000000 / N / (N - 1) tmp2 = [] for x in Y: tmp2.append(0) for i in range(N): for j in range(i+1, N): tmp2[-1] = max(tmp2[-1], abs(x[i] - x[j])) tmp2[-1] = 10000000 / sqrt(tmp2[-1] / 20 + 1) ans1 = round(sum(tmp1) / K) ans2 = round(sum(tmp2) / K) return ans1 * ans2 from random import randint, random N, K = miinput() MAXBE = 10**3 START_TEMP = 10000000 END_TEMP = 1000 T = liinput() U = liinput() Bs = [randint(1, MAXBE) for _ in [0] * N] Ms = [] for b in Bs: Ms.append(randint(1, b)) Es = [randint(1, MAXBE) for _ in [0] * N] tmp_score = score() while time() - S < 1.8: idx = randint(0, N-1) newb = randint(1, MAXBE) newm = randint(1, newb) newe = randint(1, MAXBE) oldb = Bs[idx] oldm = Ms[idx] olde = Es[idx] Bs[idx], Ms[idx], Es[idx] = newb, newm, newe new_score = score() temp = START_TEMP + (END_TEMP - START_TEMP) * time() / 2 if exp((new_score - tmp_score) / temp) < random(): Bs[idx], Ms[idx], Es[idx] = oldb, oldm, olde else: tmp_score = new_score # print(tmp_score) for b, m, e in zip(Bs, Ms, Es): print(b, m, e) # print(score() * 50) from time import time S = time() main()