QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#471364 | #7877. Balanced Array | Zaunese | WA | 0ms | 7688kb | C++14 | 1.6kb | 2024-07-10 20:45:18 | 2024-07-10 20:45:18 |
Judging History
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'