UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#138325#8. 小w、小j和小zint321012ms1404kbC++11801b2021-09-20 12:27:192021-09-20 12:27:20

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const long double inf=INT_MAX;
typedef long double ldb;
const ldb eps=1e-7;
int n, k;ldb l, r=inf, mid;
struct pep{ldb pos, vel;
bool operator <(const pep& p) const
{return pos<p.pos;}}a[N];ldb b[N];
bool equal(const ldb& x, const ldb& y)
{return (x+eps>y)&&(x-eps<y);}
bool check(ldb t)
{int res=0;for(int i=1;i<=n;i++)
{ldb x=a[i].pos+a[i].vel*t;
if(!res||b[res]<x) b[++res]=x;
if(res&&equal(b[res],x)) continue;
int f=upper_bound(b+1,b+res+1,x)-b;
b[f]=x;}return res+k>=n;}
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i].pos>>a[i].vel;
	sort(a+1,a+n+1);
	while(l+eps<r)
	{mid=(l+r)/2.0;if(check(mid)) l=mid;else r=mid;}
	if(equal(inf,r)) puts("Forever");
	else printf("%.2Lf",l);
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 1312kb

input:

20 10
-715624307 -28629151
957936621 17210368
-753657459 59049
-40974960 5153632
-402454312 -3450252...

output:

11.40

result:

ok answer is 11.3999000000

Test #2:

score: 0
Accepted
time: 0ms
memory: 1312kb

input:

20 7
-715624307 -310
957936621 3
-753657459 1
-40974960 5
-402454312 -7424
874144191 -4
-227392025 7...

output:

5850568.50

result:

ok answer is 5850568.5000000000

Test #3:

score: 0
Accepted
time: 0ms
memory: 1316kb

input:

20 4
-715624307 -1
957936621 3
-753657459 6
-40974960 1
-402454312 -1
874144191 -2
-227392025 9
-808...

output:

3926260.00

result:

ok answer is 3926260.0000000000

Test #4:

score: 0
Accepted
time: 0ms
memory: 1312kb

input:

20 6
-715624307 -1
957936621 3
-753657459 1
-40974960 1
-402454312 -119
874144191 -1
-227392025 359
...

output:

9635550.83

result:

ok answer is 9635550.8333000001

Test #5:

score: 0
Accepted
time: 0ms
memory: 1276kb

input:

20 10
-715624307 740210959
-955556582 -615695756
-24759231 771301784
-80855559 560021841
-892686343 ...

output:

Forever

result:

ok OK, forever!

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 1ms
memory: 1316kb

input:

200 10
-487405787 3200000
725249085 28629151
-671026855 -4084101
38046635 45435424
-188495128 643634...

output:

0.00

result:

wrong answer expected 0.0039000000, found 0.0000000000

Subtask #3:

score: 0
Skipped

Subtask #4:

score: 0
Wrong Answer

Test #18:

score: 15
Accepted
time: 6ms
memory: 1404kb

input:

2000 10
882856800 -387420489
866607093 -134217728
481381898 1
-488180557 1953125
-783185249 -19683
-...

output:

0.00

result:

ok answer is 0.0001000000

Test #19:

score: 0
Accepted
time: 3ms
memory: 1400kb

input:

2000 10
882856800 -177147
866607093 -48828125
481381898 1
-488180557 48828125
-783185249 -362797056
...

output:

0.00

result:

ok answer is 0.0001000000

Test #20:

score: -15
Wrong Answer
time: 2ms
memory: 1400kb

input:

2000 10
882856800 -1
866607093 -396
481381898 21
-488180557 6
-783185249 -10
-816111307 -33761
99248...

output:

2.62

result:

wrong answer expected 2.6237000000, found 2.6200000000

Subtask #5:

score: 0
Skipped

Subtask #6:

score: 0
Skipped