結果

問題 No.2368 I love a square root of 2
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2023-06-30 23:12:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,412 ms / 2,000 ms
コード長 1,498 bytes
コンパイル時間 1,547 ms
コンパイル使用メモリ 86,672 KB
実行使用メモリ 104,192 KB
最終ジャッジ日時 2023-09-21 17:30:06
合計ジャッジ時間 13,535 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 134 ms
77,860 KB
testcase_01 AC 136 ms
77,728 KB
testcase_02 AC 1,412 ms
104,184 KB
testcase_03 AC 158 ms
78,528 KB
testcase_04 AC 153 ms
78,816 KB
testcase_05 AC 157 ms
78,628 KB
testcase_06 AC 154 ms
78,728 KB
testcase_07 AC 143 ms
78,300 KB
testcase_08 AC 155 ms
78,496 KB
testcase_09 AC 152 ms
79,028 KB
testcase_10 AC 154 ms
78,472 KB
testcase_11 AC 158 ms
78,548 KB
testcase_12 AC 155 ms
78,492 KB
testcase_13 AC 1,113 ms
100,040 KB
testcase_14 AC 1,103 ms
97,960 KB
testcase_15 AC 1,219 ms
100,800 KB
testcase_16 AC 830 ms
94,320 KB
testcase_17 AC 163 ms
79,140 KB
testcase_18 AC 179 ms
81,984 KB
testcase_19 AC 179 ms
82,132 KB
testcase_20 AC 177 ms
81,820 KB
testcase_21 AC 1,318 ms
103,288 KB
testcase_22 AC 1,328 ms
104,192 KB
権限があれば一括ダウンロードができます

ソースコード

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