QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#200017#7344. Those Russian HackersDelay_for_five_minutes#WA 23ms67680kbC++203.2kb2023-10-04 15:06:012023-10-04 15:06:02

Judging History

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

  • [2023-10-04 15:06:02]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:67680kb
  • [2023-10-04 15:06:01]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
double p[300005];
int n , k;
double q[600005];
double f[300005];
typedef double db;
const int N = 1<<20 ;
const db pi2 = acos(-1) * 2;
struct cp {
    db x,y;
    inline cp() {x = y = 0;} 
    inline cp(db a,db b) {x=a,y=b;}
    inline cp operator+(const cp& p) const {return cp(x+p.x , y+p.y) ;}
    inline cp operator-(const cp& p) const {return cp(x-p.x , y-p.y) ;}
    inline cp operator*(const cp& p) const {return cp(x*p.x - y*p.y, x*p.y + y*p.x) ;}
    inline cp conj() {
        return cp(x , -y) ;
    }
}w[N]; 
int re[N] ;
inline int getre(int n)
{
    int len = 1 , bit = 0;
    while(len < n) ++bit , len <<= 1;
    for(int i = 1;i < len;i++) re[i] = (re[i>>1]>>1)|((i&1)<<(bit-1)) ;
    return len;
}
inline void init0() {
    for(int i =0 ;i < N;i++) w[i] = cp(cos(pi2*i/N) , sin(pi2*i/N));
}
void fft(cp *a,int n,int m) {
    for(int i = 1;i < n;i++) if(i < re[i]) swap(a[i] , a[re[i]]) ;
    for(int k=1,r=N>>1 ; k < n ; k <<= 1 , r >>= 1) {
        for(int i = 0;i < n;i+=(k<<1)) {
            for(int j = 0;j < k;j++) {
                cp &L = a[i + j] , &R = a[i+j+k] , t=w[r*j]*R ;
                R = L-t , L=L+t;
            }
        }
    }
    if(!~m) {
        reverse(a+1,a+n);
        cp tmp = cp(1.0/n , 0) ;
        for(int i = 0;i < n;i++) a[i] = a[i] * tmp ;
    }
    return ;
}
double preq[600005];
cp x1[N] , x2[N] ;
double h[300005];

double sufp[300005]; ///后i个p的和
double prepf[300005];
double g[300005]; ///钦定从i开始赢
double wg[300005];
int main()
{
    scanf("%d%d",&n,&k) ;
    for(int i = 0;i < n;i++) {scanf("%lf",&p[i]) ; }
    for(int i = 1;i <= n*2-2;i++) scanf("%lf",&q[i]) ;
    init0() ;
    sufp[0] = 0;
    for(int i = 1;i <= n;i++) sufp[i] = sufp[i - 1] + p[n - i] ;
    
    for(int i = 0;i < n;i++) x1[i].x = sufp[i] ;
    for(int i = 1;i <= n*2-2;i++) x2[i].x = q[i] ;
    int s = getre(3*n - 2) ;
    fft(x1 , s , 1) ; fft(x2 , s , 1) ;
    for(int i = 0;i < s;i++) x1[i] = x1[i] * x2[i] ;
    fft(x1 , s , -1);

    for(int i = n ; i < 2*(n ) ;i++) {
        f[n-1-(i - n)] = x1[i].x ;
    }
    preq[0] = 0;
    for(int i = 1;i <= 2*n - 2;i++) preq[i] = preq[i - 1] + q[i] ;
    for(int i = 0;i < n;i++) {
        f[i] += preq[n - 1 - i] ;
    }
    for(int i = 0;i < n ;i++) {
        // printf("I %d %lf\n",i,x1[i].x) ;
        g[n-i] = x1[i].x ;
    }
    for(int i = n - 2;i >= 0;i--) g[i] += g[i + 1];

    
    for(int i = 0;i < n ;i++) {
        h[k] += p[i] * preq[n-1-i] ;
        wg[i] = p[i] * preq[n-1-i];
        if(i > 0) wg[i] += wg[i - 1];
    }
    for(int i = 0;i < n ;i++) {
        prepf[i] = p[i] * f[i] ;
        if(i > 0) prepf[i] += prepf[i - 1];
    }
    sufp[n] =0;
    for(int i = n - 1;i >= 0;i--) {
        sufp[i] = sufp[i + 1] + p[i] ;
    }
    for(int i = k - 1;i >= 1;i--) {
        int pos = (lower_bound(f + 0 , f + n , h[i + 1]) - f) ;
        h[i] = prepf[pos] + sufp[pos + 1] * h[i + 1] ;
    }

    double ans = h[1] ;
    for(int i = 0;i < n;i++) {
        // printf("%lf %lf\n",wg[i - 1] , g[i]) ;
        ans = max(ans , wg[i - 1] + g[i] );
    }
    printf("%.12lf\n" , ans) ;
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 23ms
memory: 67680kb

input:

3 1
0.5 0.25 0.25
0.75 0.25 0.0 0.0

output:

0.687500000000

result:

ok found '0.6875000', expected '0.6875000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 20ms
memory: 67660kb

input:

3 2
0.3 0.4 0.3
0.0 0.0 0.0 1.0

output:

0.090000000000

result:

ok found '0.0900000', expected '0.0900000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 23ms
memory: 67604kb

input:

3 1
0.5 0.2 0.3
1.0 0.0 0.0 0.0

output:

0.800000000000

result:

ok found '0.8000000', expected '0.8000000', error '0.0000000'

Test #4:

score: 0
Accepted
time: 19ms
memory: 67600kb

input:

2 1
1.0 0.0
0.7 0.3

output:

0.700000000000

result:

ok found '0.7000000', expected '0.7000000', error '0.0000000'

Test #5:

score: -100
Wrong Answer
time: 23ms
memory: 67536kb

input:

2 2
0.0 1.0
0.6 0.4

output:

0.000000000000

result:

wrong answer 1st numbers differ - expected: '0.6000000', found: '0.0000000', error = '0.6000000'