QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#753747#5983. Pretty Good ProportionXY_Eleven0 2296ms39980kbC++202.4kb2024-11-16 13:33:022024-11-16 13:33:02

Judging History

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

  • [2024-11-16 13:33:02]
  • 评测
  • 测评结果:0
  • 用时:2296ms
  • 内存:39980kb
  • [2024-11-16 13:33:02]
  • 提交

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'