Submission #60537

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
//include <bits/stdc++.h>
// Headder {{{
#pragma GCC optimize("Ofast")
#include <complex>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <climits>
// }}}
using namespace std;
#define read cin >>
#define echo cout <<
#define fin << '\n'
#define _ << ' ' <<
#define in :
#define var auto&&
#define let const auto
#define double float
int sq[3000000];
int dp[3000000];
int f ( int r, int l ) {
if ( ~dp[r] ) return dp[r];
int sum = 0;
int rng_58 = min(sq[r], l);
for ( int x = 0; x <= rng_58; x++ ) {
sum += min ( l+1, 1 + sq[r - x*x] );
}
return dp[r] = sum;
}
struct Data {
int l, k, i;
bool operator < ( const Data &a ) {
return this->l < a.l;
}
bool operator > ( const Data &a ) {
return this->l > a.l;
}
};
struct Ans {
int i, ans;
bool operator < ( const Ans &a ) {
return this->i < a.i;
}
bool operator > ( const Ans &a ) {
return this->i > a.i;
}
};
Data data[100000];
Ans ans[100000];
signed main ( ) {
int a = 0;
for ( int i = 0; i < 3000000; i++ ) {
if ( i < (a+1) * (a+1) ) sq[i] = a;
else {
++a;
sq[i] = a;
}
}
int t;
scanf("%d", &t);
int kai = 25;
for ( int I = 0; I < t; I++ ) {
int l, k;
scanf("%d %d", &l, &k);
data[I] = {l, k, I};
}
sort(data, data+t);
int bef = -1;
for ( int I = 0; I < t; I++ ) {
int l = data[I].l;
int k = data[I].k;
if ( l != bef ) {
memset(dp, -1, sizeof(dp));
bef = l;
}
int ng = sq[k]-1;
int ok = 3*l*l;
for ( int i = 0; i < kai; i++ ) {
int mid = ( ok + ng ) / 2;
if ( f ( mid, l ) >= k ) ok = mid;
else ng = mid;
}
ans[I] = {data[I].i, ok};
}
sort(ans, ans+t);
for ( int i = 0; i < t; i++ ) {
printf("%.06lf\n", sqrt(ans[i].ans));
}
return 0;
}

ステータス

項目 データ
問題 1353 - Function of Euclidean Distance
ユーザー名 r1825
投稿日時 2020-07-10 06:44:24
言語 C++14
状態 Accepted
得点 400
ソースコード長 2402 Byte
最大実行時間 1363 ms
最大メモリ使用量 36468 KB

セット

セット 得点 Cases
1 task01 60 / 60 in01*, sample01.txt
2 task02 340 / 340 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01_01.txt AC 30 ms 24028 KB
1
2
in01_02.txt AC 21 ms 23856 KB
1
2
in01_03.txt AC 29 ms 23808 KB
1
2
in01_04.txt AC 31 ms 23892 KB
1
2
in01_05.txt AC 23 ms 23972 KB
1
2
in01_06.txt AC 31 ms 23924 KB
1
2
in01_07.txt AC 24 ms 23876 KB
1
2
in01_08.txt AC 31 ms 23956 KB
1
2
in01_09.txt AC 24 ms 23904 KB
1
2
in01_10.txt AC 24 ms 23980 KB
1
2
in02_01.txt AC 100 ms 27128 KB
2
in02_02.txt AC 111 ms 28208 KB
2
in02_03.txt AC 503 ms 29292 KB
2
in02_04.txt AC 76 ms 30116 KB
2
in02_05.txt AC 65 ms 31200 KB
2
in02_06.txt AC 1362 ms 32284 KB
2
in02_07.txt AC 1298 ms 33236 KB
2
in02_08.txt AC 1280 ms 34316 KB
2
in02_09.txt AC 1353 ms 35392 KB
2
in02_10.txt AC 1363 ms 36468 KB
2
sample01.txt AC 28 ms 34476 KB
1
2
sample02.txt AC 37 ms 34428 KB
2