QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#471364#7877. Balanced ArrayZauneseWA 0ms7688kbC++141.6kb2024-07-10 20:45:182024-07-10 20:45:18

Judging History

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

  • [2024-07-10 20:45:18]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7688kb
  • [2024-07-10 20:45:18]
  • 提交

answer

//#define dxx
#ifdef dxx
#define dbg(...) fprintf(stderr,__VA_ARGS__)
#endif

#include<cstdio>
#include<cstring>
#include<algorithm>

#define fi first
#define se second
using ll=long long;
using std::max;
using std::min;
template<class T> void cmax(T&a,T b){a=max(a,b);}
template<class T> void cmin(T&a,T b){a=min(a,b);}

/*
   k satisfied,so k|V,Vsatisfied
   lastsitisfiedN for k <= ~ for V,k|V
   algorithm: when append,check every k
 */

const int NV=2e6;
const int mod=1e9+9,bas=230941340;
int ksm(int a,int p){
    int ans=1;
    while(p){
        if(p&1) ans=(ll)ans*a%mod;
        a=(ll)a*a%mod;
        p>>=1;
    }return ans;
}

namespace xm{
    int a[NV+5],pw[NV+5],ipw[NV+5],has[NV+5],kln[NV+5];
    int hash(int l,int r){
        return ll(has[r]-has[l-1]+mod)*ipw[l]%mod;
    }void _(){
        int N;
        const int iB=ksm(bas,mod-2);

        scanf("%d",&N);
        pw[0]=1;
        for(int i=1;i<=N;++i) pw[i]=(ll)pw[i-1]*bas%mod;
        ipw[0]=1;
        for(int i=1;i<=N;++i) ipw[i]=(ll)ipw[i-1]*iB%mod;

        for(int i=1;i<=N;++i){
            scanf("%d",a+i);
            has[i]=(has[i-1]+(ll)a[i]*pw[i])%mod;
        }

        for(int k=1,p=1;k*2+1<=N;++k){
            cmax(p,k*2+1);
            for(;;)
                if((hash(1,p-k*2)+hash(k*2+1,p))%mod
                        ==hash(k+1,p-k)*2%mod) ++p;
                else break;
            kln[k]=p;
        }
        for(int i=2;i*2+1<=N;++i) cmax(kln[i],kln[i-1]);
        for(int i=1;i<=N;++i) putchar(kln[(i-1)/2]>i?'1':'0');
        putchar(10);
    }
}

int main(){
    xm::_();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 7688kb

input:

3
1 2 3

output:

001

result:

ok single line: '001'

Test #2:

score: 0
Accepted
time: 0ms
memory: 7500kb

input:

9
1 2 3 2 5 4 3 8 5

output:

001010111

result:

ok single line: '001010111'

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 7668kb

input:

9
1C 3f 4S 3h 88 6x 4W d1 8c

output:

000000000

result:

wrong answer 1st lines differ - expected: '001010111', found: '000000000'