Submission #60539

ソースコード

?
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
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
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);
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 < 25; 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 07:38:36
言語 C++14
状態 Accepted
得点 400
ソースコード長 1817 Byte
最大実行時間 1491 ms
最大メモリ使用量 36468 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01_01.txt AC 36 ms 24028 KB
1
2
in01_02.txt AC 31 ms 23988 KB
1
2
in01_03.txt AC 30 ms 23820 KB
1
2
in01_04.txt AC 29 ms 23776 KB
1
2
in01_05.txt AC 31 ms 23988 KB
1
2
in01_06.txt AC 26 ms 23944 KB
1
2
in01_07.txt AC 30 ms 23900 KB
1
2
in01_08.txt AC 27 ms 23992 KB
1
2
in01_09.txt AC 30 ms 24084 KB
1
2
in01_10.txt AC 35 ms 23908 KB
1
2
in02_01.txt AC 99 ms 27064 KB
2
in02_02.txt AC 109 ms 28284 KB
2
in02_03.txt AC 505 ms 29372 KB
2
in02_04.txt AC 64 ms 30072 KB
2
in02_05.txt AC 71 ms 31028 KB
2
in02_06.txt AC 1481 ms 32116 KB
2
in02_07.txt AC 1452 ms 33204 KB
2
in02_08.txt AC 1479 ms 34292 KB
2
in02_09.txt AC 1422 ms 35376 KB
2
in02_10.txt AC 1491 ms 36468 KB
2
sample01.txt AC 26 ms 34484 KB
1
2
sample02.txt AC 29 ms 34568 KB
2