ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#173856 | #8. 小w、小j和小z | zhzhallen | 0 | 708ms | 1296kb | C++ | 1.3kb | 2023-07-20 17:20:20 | 2023-07-20 17:20:22 |
answer
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 1e5 + 10;
const int eps = 1e-8;
const int INF = 1e9 +10;
struct people {
int p,v,tmp;
} f[N];
long double g[N];
int n,k;
bool cmp(people A,people B)
{
return A.p < B.p;
}
bool cmp1(people A,people B)
{
return A.tmp < B.tmp;
}
int check(double mid){
for (int i = 1; i <= n; i ++ )
f[i].tmp = f[i].p + f[i].v*mid;
sort(f + 1, f + n + 1,cmp);
int t = 0;
for (int i = 1; i <= n; i ++ )
{
if(!t || g[t] < f[i].tmp) g[++ t] = f[i].tmp;
if(t && fabs(g[t]-f[i].tmp) < eps) continue;
g[upper_bound(g + 1, g + t + 1,f[i].tmp)-g] = f[i].tmp;
}
return t + k >= n;
}
int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i ++ )
{
int p,v;
cin >> p >> v;
f[i] = (people){p,v};
}
sort(f + 1,f + 1 + n, cmp);
double l = 0,r = INF + 1,mid;
for(int i = 1; i <= log2(INF)*log2(INF); i ++ ) {
mid = (l + r)/2.0;
if(check(mid)) l = mid;
else r = mid;
}
if(mid > INF/5) return puts("FOREVER"),0;
return printf("%.4lf",mid),0;
}
Details
小提示:点击横条可展开更详细的信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 10
Accepted
time: 0ms
memory: 1244kb
input:
20 10 -715624307 -28629151 957936621 17210368 -753657459 59049 -40974960 5153632 -402454312 -3450252...
output:
11.3999
result:
ok answer is 11.3999000000
Test #2:
score: 0
Accepted
time: 1ms
memory: 1248kb
input:
20 7 -715624307 -310 957936621 3 -753657459 1 -40974960 5 -402454312 -7424 874144191 -4 -227392025 7...
output:
5850568.4000
result:
ok answer is 5850568.5000000000
Test #3:
score: 0
Accepted
time: 0ms
memory: 1248kb
input:
20 4 -715624307 -1 957936621 3 -753657459 6 -40974960 1 -402454312 -1 874144191 -2 -227392025 9 -808...
output:
3926259.5000
result:
ok answer is 3926260.0000000000
Test #4:
score: 0
Accepted
time: 0ms
memory: 1244kb
input:
20 6 -715624307 -1 957936621 3 -753657459 1 -40974960 1 -402454312 -119 874144191 -1 -227392025 359 ...
output:
9635550.7692
result:
ok answer is 9635550.8333000001
Test #5:
score: -10
Wrong Answer
time: 0ms
memory: 1240kb
input:
20 10 -715624307 740210959 -955556582 -615695756 -24759231 771301784 -80855559 560021841 -892686343 ...
output:
2.4534
result:
wrong answer Wrong answer!
Subtask #2:
score: 0
Wrong Answer
Test #6:
score: 20
Accepted
time: 9ms
memory: 1244kb
input:
200 10 -487405787 3200000 725249085 28629151 -671026855 -4084101 38046635 45435424 -188495128 643634...
output:
0.0039
result:
ok answer is 0.0039000000
Test #7:
score: 0
Accepted
time: 9ms
memory: 1244kb
input:
200 10 -487405787 1 725249085 65536 -671026855 -100000000 38046635 1679616 -188495128 6561 -73172885...
output:
0.0042
result:
ok answer is 0.0041000000
Test #8:
score: 0
Accepted
time: 9ms
memory: 1248kb
input:
200 10 -487405787 3 725249085 2 -671026855 -6 38046635 5 -188495128 14 -731728859 12 -331220744 2 31...
output:
14398.5166
result:
ok answer is 14398.5188000000
Test #9:
score: 0
Accepted
time: 9ms
memory: 1252kb
input:
200 10 -487405787 56 725249085 2 -671026855 -8 38046635 1 -188495128 252 -731728859 28 -331220744 2 ...
output:
8320.3680
result:
ok answer is 8320.3684000000
Test #10:
score: 0
Accepted
time: 9ms
memory: 1248kb
input:
200 10 -487405787 11 725249085 8 -671026855 -1 38046635 1 -188495128 125 -731728859 106 -331220744 4...
output:
543.5187
result:
ok answer is 543.5186000000
Test #11:
score: -20
Wrong Answer
time: 9ms
memory: 1240kb
input:
200 10 -584283703 -467650291 -389608337 -287739809 -372147316 -257836606 175915600 328991856 7355243...
output:
1.1755
result:
wrong answer Wrong answer!
Subtask #3:
score: 0
Skipped
Subtask #4:
score: 0
Wrong Answer
Test #18:
score: 15
Accepted
time: 108ms
memory: 1296kb
input:
2000 10 882856800 -387420489 866607093 -134217728 481381898 1 -488180557 1953125 -783185249 -19683 -...
output:
0.0002
result:
ok answer is 0.0001000000
Test #19:
score: 0
Accepted
time: 108ms
memory: 1292kb
input:
2000 10 882856800 -177147 866607093 -48828125 481381898 1 -488180557 48828125 -783185249 -362797056 ...
output:
0.0001
result:
ok answer is 0.0001000000
Test #20:
score: 0
Accepted
time: 107ms
memory: 1288kb
input:
2000 10 882856800 -1 866607093 -396 481381898 21 -488180557 6 -783185249 -10 -816111307 -33761 99248...
output:
2.6236
result:
ok answer is 2.6237000000
Test #21:
score: 0
Accepted
time: 119ms
memory: 1296kb
input:
2000 10 882856800 -3 866607093 -2 481381898 12 -488180557 8639109 -783185249 -12 -816111307 -96 9924...
output:
0.0008
result:
ok answer is 0.0008000000
Test #22:
score: 0
Accepted
time: 104ms
memory: 1296kb
input:
2000 10 882856800 -1 866607093 -10 481381898 406927 -488180557 1 -783185249 -1483 -816111307 -8 9924...
output:
0.0003
result:
ok answer is 0.0003000000
Test #23:
score: -15
Wrong Answer
time: 107ms
memory: 1288kb
input:
2000 10 784172079 808971860 81381899 71917076 -712636352 -738530531 -622770179 -640667385 119667134 ...
output:
1.1482
result:
wrong answer Wrong answer!
Subtask #5:
score: 0
Skipped
Subtask #6:
score: 0
Skipped