QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#732901#5983. Pretty Good ProportionDengDuck27 ✓1186ms23492kbC++14837b2024-11-10 16:21:452024-11-10 16:21:45

Judging History

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

  • [2024-11-10 16:21:45]
  • 评测
  • 测评结果:27
  • 用时:1186ms
  • 内存:23492kb
  • [2024-11-10 16:21:45]
  • 提交

answer

#include<bits/stdc++.h>
#define LF long double
using namespace std;
const int N=5e5+5;
const LF E=1e-14;
LF P,Ans;
struct Node{int X;LF Y;}B[N];
int n,A[N],S[N],Pl;
inline LF Cal(Node A,Node B){return (B.Y-A.Y)/(B.X-A.X);}
inline void Upd(int x,LF K)
{
	if(K<Ans-E||fabs(Ans-K)<=E&&x<Pl)Pl=x,Ans=K;
}
inline void DP()
{
	for(int i=1;i<=n;i++)
	{
		S[i]=S[i-1]+A[i];
		B[i]={i,P*i-S[i]};
	}
	B[0]={0,0};
	sort(B,B+n+1,[](Node X,Node Y){return X.Y<Y.Y;});
	for(int i=0;i<n;i++)
	{
		if(B[i].X<B[i+1].X)Upd(B[i].X,Cal(B[i],B[i+1]));
	}
}
inline int Work()
{
	Ans=1e9,Pl=0;
	scanf("%d%Lf",&n,&P);
	for(int i=1;i<=n;i++)scanf("%1d",&A[i]);
	DP();

	for(int i=1;i<=n;i++)A[i]^=1;
	P=1-P,DP();
	return Pl;
}
int main()
{
	int T;scanf("%d",&T);
	for(int i=1;i<=T;i++)printf("Case #%d: %d\n",i,Work());
}

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 4ms
memory: 8016kb

input:

100
10 0.827672
0010101011
4 0.932623
0100
1000 0.834002
011001110010111110000110101100010010100101101110110111100010101101111100110001011000110100010100011011000001100001010110111101111010110110000110011000111000011110101100100111111001111011011100111001011101010100111011100011110011100011110010001...

output:

Case #1: 6
Case #2: 1
Case #3: 10
Case #4: 0
Case #5: 0
Case #6: 1
Case #7: 0
Case #8: 0
Case #9: 0
Case #10: 0
Case #11: 0
Case #12: 4
Case #13: 5
Case #14: 564
Case #15: 0
Case #16: 0
Case #17: 0
Case #18: 0
Case #19: 0
Case #20: 0
Case #21: 0
Case #22: 0
Case #23: 0
Case #24: 844
Case #25: 0
Case...

result:

ok 100 lines

Subtask #2:

score: 22
Accepted

Test #2:

score: 22
Accepted
time: 1186ms
memory: 23492kb

input:

100
15 0.333333
000000000011000
10 0.418754
0101100001
2 0.499999
01
3 0.977951
001
2 0.249999
01
10 0.670229
0111011001
1000 0.500001
001101111110110010110000010010110001110010001101110111010011000010100011011101010110011011011010111110011100011000001000101011100011010100101101111110100101011010111...

output:

Case #1: 6
Case #2: 0
Case #3: 0
Case #4: 2
Case #5: 0
Case #6: 0
Case #7: 0
Case #8: 0
Case #9: 0
Case #10: 0
Case #11: 0
Case #12: 0
Case #13: 0
Case #14: 0
Case #15: 0
Case #16: 4333
Case #17: 0
Case #18: 0
Case #19: 123
Case #20: 0
Case #21: 0
Case #22: 0
Case #23: 0
Case #24: 0
Case #25: 0
Case...

result:

ok 100 lines

Extra Test:

score: 0
Extra Test Passed