QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#753747 | #5983. Pretty Good Proportion | XY_Eleven | 0 | 2296ms | 39980kb | C++20 | 2.4kb | 2024-11-16 13:33:02 | 2024-11-16 13:33:02 |
Judging History
answer
#include <bits/stdc++.h>
#define For(e,e1,e2) for(int e=(e1);e<=(e2);e++)
#define For_(e,e1,e2) for(int e=(e1);e<(e2);e++)
#define Rof(e,e1,e2) for(int e=(e2);e>=(e1);e--)
#define Rof_(e,e1,e2) for(int e=(e2);e>(e1);e--)
#define exc(e) if(e) continue
#define stop(e) if(e) break
#define ret(e) if(e) return
#define LL long long
#define ULL unsigned long long
#define DB double
#define cint const int
#define cLL const long long
#define vct vector
#define pb push_back
#define ft first
#define sc second
using namespace std;
void main_init()
{
}
cint N=1.02e6;
int n;
char str[N];
int a[N],c[N],h[N],h2[N],fin[N];
DB f,d[N];
pair<DB,int> d_[N];
const DB eps=4e-13;
void input()
{
scanf("%d%lf%s",&n,&f,str+1);
reverse(str+1,str+n+1);
a[0]=0; For(i,1,n) a[i]=a[i-1]+(str[i]-'0');
}
void Add(int k)
{
for(int i=k;i<=n;i+=(i&-i))
c[i]++;
}
int Sum(int k)
{
int w=0;
for(int i=k;i;i^=(i&-i))
w+=c[i];
return w;
}
void srt(DB w)
{
For(i,1,n) d_[i]={d[i]=(DB)a[i]-w*i,i};
sort(d_+1,d_+n+1);
}
bool same(DB w)
{
For(i,1,n) d[i]=(DB)a[i]-w*i;
For_(i,1,n) if(d[d_[i].sc]>d[d_[i+1].sc]) return false;
return true;
}
LL check(DB w)
{
srt(w);
For(i,1,n) fin[d_[i].sc]=i;
For(i,1,n) c[i]=0;
LL t=0ll;
For(i,1,n)
{
t+=(h[i]=Sum(fin[i]));
Add(fin[i]);
}
return t;
}
int gt(DB w1,DB w2)
{
// printf("get %.20lf %.20lf\n",w1,w2);
check(w1); For(i,1,n) h2[i]=h[i];
check(w2); Rof(i,1,n) if(h[i]!=h2[i]) return i;
return n;
}
void main_solve()
{
input();
DB w1=2.0,w2=-2.0;
srt(f-eps);
DB l=f,r=(DB)1.0,mid;
while(l+eps<r)
((same(mid=(l+r)/2.0))?l:r)=mid;
r+=eps; if(!same(r)) w1=r;
// printf("r=%lf\n",r);
srt(f+eps);
l=(DB)0.0,r=f,mid;
while(l+eps<r)
((same(mid=(l+r)/2.0))?r:l)=mid;
l-=eps; if(!same(l)) w2=l;
// printf("l=%lf\n",l);
DB t=fabs(w1-f)-fabs(w2-f);
int k;
if(fabs(t)<=eps*1.5) k=max(gt(f-eps,w1),gt(f+eps,w2));
else if(t<(DB)0.0) k=gt(f-eps,w1);
else k=gt(f+eps,w2);
printf("%d\n",n-k);
}
int main()
{
// freopen("ex_binary3.in","r",stdin);
main_init();
int _; scanf("%d",&_); For(__,1,_)
{
printf("Case #%d: ");
main_solve();
}
return 0;
}
/*
*/
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 18240kb
input:
100 10 0.827672 0010101011 4 0.932623 0100 1000 0.834002 011001110010111110000110101100010010100101101110110111100010101101111100110001011000110100010100011011000001100001010110111101111010110110000110011000111000011110101100100111111001111011011100111001011101010100111011100011110011100011110010001...
output:
Case #0: 2 Case #0: 1 Case #0: 10 Case #0: 0 Case #0: 0 Case #0: 1 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 5 Case #0: 564 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 844 Case #0: 0 Case #0: 0 Case #0: ...
result:
wrong answer 1st lines differ - expected: 'Case #1: 6', found: 'Case #0: 2'
Subtask #2:
score: 0
Wrong Answer
Test #2:
score: 0
Wrong Answer
time: 2296ms
memory: 39980kb
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 #0: 6 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 4333 Case #0: 0 Case #0: 0 Case #0: 123 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: 0 Case #0: ...
result:
wrong answer 1st lines differ - expected: 'Case #1: 6', found: 'Case #0: 6'