結果

問題 No.2368 I love a square root of 2
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2023-06-30 23:12:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,229 ms / 2,000 ms
コード長 1,498 bytes
コンパイル時間 204 ms
コンパイル使用メモリ 82,260 KB
実行使用メモリ 102,972 KB
最終ジャッジ日時 2024-07-07 11:08:12
合計ジャッジ時間 10,004 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

31063 96955 * (2**0.5) = 168178
2 * 10**6 位まで
二分探索も許されそうだな…

まず、1の位を決め打つか

候補を絞ってsortするのかなぁ

"""

import sys
from sys import stdin
import heapq

def cmp( a , b ):

    if a == b:
        return 0

    x = a[0] - b[0]
    y = a[1] - b[1]

    if x <= 0 and y <= 0:
        return -1
    elif x >= 0 and y >= 0:
        return 1

    if x < 0:
        if 2*(y**2) < x**2:
            return -1
        else:
            return 1
    else:
        if x**2 < 2*(y**2):
            return -1
        else:
            return 1

N = int(input())

L = 0
R = 168200

while R-L != 1:

    M = (L+R)//2
    now = 0

    for i in range(0,M+1):

        xfloat = ( (M-i)**2 / 2 ) ** 0.5

        x = None
        for xint in range(max(1,int(xfloat)-3) , int(xfloat) + 3):
            if 2 * (xint**2) > (M-i)**2:
                x = xint-1
                break

        now += x+1

    if now >= N:
        R = M
    else:
        L = M


rems = []

for i in range(0,R+1):
    
    xfloat = ( (R-i)**2 / 2 ) ** 0.5

    x = None
    for xint in range(max(1,int(xfloat)-3) , int(xfloat) + 3):
            if 2 * (xint**2) > (R-i)**2:
                x = xint-1
                break

    # 一番大きい奴が、R-1以上か? を見る

    maxa = i
    maxb = x
    rems.append( (maxa,maxb) )

    N -= x

from functools import cmp_to_key

ans = list(sorted(rems , key=cmp_to_key(cmp)))
#print (N,ans,R)

print (*ans[N-1])
0