QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#727992 | #5983. Pretty Good Proportion | BigJoker | 0 | 2300ms | 44732kb | C++14 | 1.1kb | 2024-11-09 14:19:21 | 2024-11-09 14:19:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n;
int a[N],sx[N],sy[N];
double f[N],p;
set<pair<double,int> >S;
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int _;
cin>>_;
while(_--){
cin>>n>>p;
for(int i=1;i<=n;i++){
char x;
cin>>x;
a[i]=x-'0';
sx[i]=sx[i-1]+a[i];
sy[i]=sy[i-1]+1;
}
for(int i=0;i<=n;i++)
f[i]=sx[i]-p*sy[i];
// for(int i=1;i<=n;i++)
// cout<<fixed<<setprecision(6)<<f[i]<<'\n';
S.clear();
double ans=1e9;
int al=n;
for(int i=n;i;i--){
S.insert(make_pair(f[i],i));
auto R=S.upper_bound(make_pair(f[i-1],114514)),L=R;
if(R!=S.end()){
int l=i,r=(*R).second;
double ret=(sx[r]-sx[l-1])/1.0/(sy[r]-sy[l-1]);
if(fabs(ret-p)<=fabs(ans-p)){
ans=ret;
al=l;
}
}
if(R!=S.begin()){
L--;
int l=i,r=(*L).second;
double ret=(sx[r]-sx[l-1])/1.0/(sy[r]-sy[l-1]);
if(fabs(ret-p)<=fabs(ans-p)){
ans=ret;
al=l;
}
}
}
cout<<al<<'\n';
}
return 0;
}
/*
1
7 0.5
1101110
4
7 0.5
1101110
11 0.8
11111011110
9 0.75
011001011
9 0.666
010111100
*/
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 5960kb
input:
100 10 0.827672 0010101011 4 0.932623 0100 1000 0.834002 011001110010111110000110101100010010100101101110110111100010101101111100110001011000110100010100011011000001100001010110111101111010110110000110011000111000011110101100100111111001111011011100111001011101010100111011100011110011100011110010001...
output:
7 2 11 1 1 2 1 1 1 1 1 5 6 565 1 1 1 1 1 1 1 1 1 845 1 1 2 156 1 1 1 1 1 1 394 2 174 1 3 1 131 4 1 841 2 6 1 1 75 1 2 1 1 1 1 1 2 1 2 1 1 1 9 1 1 839 3 3 1 1 1 613 1 6 1 1 1 1 1 1 2 1 321 1 1 7 80 1 1 1 1 1 2 1 2 159 1 1 4 1
result:
wrong answer 1st lines differ - expected: 'Case #1: 6', found: '7'
Subtask #2:
score: 0
Wrong Answer
Test #2:
score: 0
Wrong Answer
time: 2300ms
memory: 44732kb
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:
7 1 1 3 1 1 1 1 1 1 1 1 1 1 1 4334 1 1 124 1 1 1 1 1 1 1 1 4 1 682 1 1 3 1 1 1 1 1 2 3 1 289 3 2 2 1 1 1 1 1 1 1 1 2 1 2 1 6 6 1 2 2 1 3 2 1 7 4 1 501 2 1 1 2 1 2 189 4 1 7 499839 1 1 6 1 1 1 499841 1 1 9 5 1 2 1 1 1 93 1 1
result:
wrong answer 1st lines differ - expected: 'Case #1: 6', found: '7'