QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#732901 | #5983. Pretty Good Proportion | DengDuck | 27 ✓ | 1186ms | 23492kb | C++14 | 837b | 2024-11-10 16:21:45 | 2024-11-10 16:21:45 |
Judging History
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