QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#756000#8037. Gambler's Ruinbruteforce_WA 0ms4024kbC++201.6kb2024-11-16 18:41:142024-11-16 18:41:14

Judging History

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

  • [2024-11-16 18:41:14]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:4024kb
  • [2024-11-16 18:41:14]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-12;
struct node
{
	double p,v;
	int id;
	node()
	{
		p=v=id=0;
	}
	node(double a,double b,int c)
	{
		p=a; v=b; id=c;
	}
	bool operator < (const node &t)
	{
		return p>t.p;
	}
};
void O_o()
{
	int n;
	cin>>n;
//	vector<int> t(n+1);
	vector<array<double,2>> a(n+1);
	int cnt=0;
	a[0][0]=2;
	for(int i=1; i<=n; i++)
	{
		double x,y;
		cin>>x>>y;
		if(x<=eps)
			x+=eps;
		else if(1-x<=eps)
			x-=eps;
		if(fabs(x-a[cnt][0])<=eps)
		{
			a[cnt][1]+=y;
		}
		else
		{
			a[++cnt]={x,y};
		}
	}
	a.resize(cnt+1);
	sort(a.begin()+1,a.end(),greater<>());
	n=a.size()-1;
	vector<node> b(n+1);
	for(int i=1; i<=n; i++)
	{
		b[i]=node(1.0-a[i][0],a[i][1],i);
	}
	sort(b.begin()+1,b.end());
	vector<int> pos(n+1);
	for(int i=1; i<=n; i++)
		pos[b[i].id]=i;
	vector<bool> del(n+1);
	int r=1;
	double x=0,y=0,sx=0,sy=0;
	vector<int> st;
	double ans=0;
	for(int i=1; i<=n; i++)
	{
		x=1.0/a[i][0];
		sx+=a[i][1];
		if(pos[i]<r)
			sy-=a[i][1];
		del[pos[i]]=1;
		while(r<=n&&((sy+b[i].v)*(1.0/b[i].p)<=sx*x||del[r]))
		{
			if(!del[r])
			{
				sy+=b[r].v;
				st.push_back(r);
			}
			r++;
		}
		while(st.size()&&del[st.back()])
			st.pop_back();
		y=(st.empty()?0:(1.0/b[st.back()].p));
		ans=max(ans,sx+sy-max(sx*x,sy*y));
		if(r<=n&&(!del[r]))
			ans=max(ans,sx+sy+b[r].v-max(sx*x,(sy+b[r].v)*(1.0/b[r].p)));
	}
	cout<<ans<<"\n";
}
signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cout<<fixed<<setprecision(12);
	int T=1;
//	cin>>T;
	while(T--)
	{
		O_o();
	}
}









詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3840kb

input:

2
1 15
0 10

output:

9.999999999985

result:

ok found '10.0000000', expected '10.0000000', error '0.0000000'

Test #2:

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

input:

3
0.4 100
0.5 100
0.6 100

output:

33.333333333333

result:

ok found '33.3333333', expected '33.3333333', error '0.0000000'

Test #3:

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

input:

1
0 1

output:

0.000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #4:

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

input:

2
1 0
1 100

output:

0.000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #5:

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

input:

1
0.5 100

output:

0.000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #6:

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

input:

3
0.4 100
0.6 100
0.6 100

output:

0.000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #7:

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

input:

3
0.2 100
0.2 100
0.8 100

output:

50.000000000000

result:

ok found '50.0000000', expected '50.0000000', error '0.0000000'

Test #8:

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

input:

2
0.999999 1000000
0.999998 2

output:

0.999998999992

result:

ok found '0.9999990', expected '0.9999990', error '0.0000000'

Test #9:

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

input:

2
0 100000
0.000001 1

output:

0.000000000000

result:

ok found '0.0000000', expected '0.0000000', error '-0.0000000'

Test #10:

score: -100
Wrong Answer
time: 0ms
memory: 3800kb

input:

2
0 1000000000
0.000001 1

output:

0.998999953270

result:

wrong answer 1st numbers differ - expected: '1.0000000', found: '0.9990000', error = '0.0010000'