QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#378801 | #6401. Classic: N Real DNA Pots | yujianlin# | WA | 2ms | 4420kb | C++17 | 1.3kb | 2024-04-06 14:43:10 | 2024-04-06 14:43:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define eps 1e-9
#define ll long long
#define lowbit(x) ((x) & (-x))
struct Point
{
ll x,y;
}p[100010];
int a[100010],n,k;
void add(int k1,int k2)//单点修改,a[k1]加上k2
{
for(int i=k1;i<=n;i+=lowbit(i))
a[i]+=k2;
}
int sum(int z)//单点查询前z个数和(前缀和)
{
int res=0;
for(int i=z;i;i-=lowbit(i))
res+=a[i];
return res;
}
int sum(int l,int r)//区间查询,查询[l,r]区间和
{
int ans=sum(r)-sum(l-1);
return ans;
}
bool check(double x)
{
memset(a,0,sizeof(a));
vector<double> vt;
for(int i=1;i<=n;i++)
{
double now=p[i].y-p[i].x*x;
vt.push_back(now);
}
sort(vt.begin(),vt.end());
for(int i=1;i<=n;i++)
{
int id=lower_bound(vt.begin(),vt.end(),p[i].y-p[i].x*x)-vt.begin()+1;
// cout<<"####"<<id<<'\n';
add(id,1);
int ans=sum(id);
if(ans>=k)
return true;
}
return false;
}
void solve()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>p[i].x>>p[i].y;
// int cnt=0;
double l=-1e9+1,r=1e9+1;
while((r-l)>=eps)
{
// cnt+=1;
double mid=(l+r)/2;
// cout<<fixed<<setprecision(4)<<mid<<'\n';
if(check(mid))
l=mid;
else
r=mid;
// if(cnt>=2)
// break;
}
cout<<fixed<<setprecision(8)<<l<<'\n';
}
int main()
{
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4132kb
input:
4 3 1 2 2 4 3 3 4 1
output:
-1.00000000
result:
ok found '-1.0000000', expected '-1.0000000', error '-0.0000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 4244kb
input:
2 2 1 1 5 3
output:
0.50000000
result:
ok found '0.5000000', expected '0.5000000', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 4420kb
input:
2 2 222640995 547139825 489207317 725361095
output:
0.66858134
result:
ok found '0.6685813', expected '0.6685813', error '0.0000000'
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 4216kb
input:
1000 20 545612 774435015 828317 212155588 5294705 85926095 5648835 764528941 6159263 570820268 7177330 744079287 8446124 162286636 8735551 586528841 9263030 524140841 9505706 636254627 12111352 182639083 12750780 238494418 13149143 913232250 13382784 11485121 13699797 414697815 14263990 423817548 15...
output:
51.17213418
result:
wrong answer 1st numbers differ - expected: '3.7932105', found: '51.1721342', error = '12.4904548'