QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#378801#6401. Classic: N Real DNA Potsyujianlin#WA 2ms4420kbC++171.3kb2024-04-06 14:43:102024-04-06 14:43:18

Judging History

你现在查看的是最新测评结果

  • [2024-04-06 14:43:18]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4420kb
  • [2024-04-06 14:43:10]
  • 提交

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;	
} 

详细

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'