QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#188933#5475. Make a LoopBirdTL 9ms54024kbC++143.5kb2023-09-26 16:57:592023-09-26 16:57:59

Judging History

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

  • [2023-09-26 16:57:59]
  • 评测
  • 测评结果:TL
  • 用时:9ms
  • 内存:54024kb
  • [2023-09-26 16:57:59]
  • 提交

answer

#include<bits/stdc++.h>
#define N 1000000
using namespace std;
const int mod=998244353;
inline int fmod(const int &x) {return x<mod?x:x-mod;}
inline int qmod(const int &x) {return x<0?x+mod:x;}
inline void add(int &a,const int &b) {if((a+=b)>=mod) a-=mod;}
inline void sub(int &a,const int &b) {if((a-=b)<0) a+=mod;}
namespace IO
{
    const int SIZE=1<<21;
    char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55];int f,qr;
    #define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++)
    inline void flush()
    {
        fwrite(obuf,1,oS-obuf,stdout);
        oS=obuf;
    }
    inline void putc(char x)
    {
        *oS++=x;
        if(oS==oT) flush();
    }
    template<class I>
    inline void read(I &x)
    {
        for(f=1,c=gc();c<'0' || c>'9';c=gc()) if(c=='-') f=-1;
        for(x=0;c<='9' && c>='0';c=gc()){x=(x<<1)+(x<<3)+(c&15);}x*=f;
    }
    template<class I>
    inline void print(I x)
    {
        if(!x) putc('0');
        if(x<0) putc('-'),x=-x;
        while(x) qu[++qr]=x%10+'0',x/=10;
        while(qr) putc(qu[qr--]);
    }
    struct Flusher_{~Flusher_(){flush();}}io_flusher_;
}
using IO::read;
using IO::putc;
using IO::print;
inline int quick_pow(int x,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1) ret=1ll*ret*x%mod;
        x=1ll*x*x%mod,b>>=1;
    }
    return ret;
}
inline int inv(int x) {return quick_pow(x,mod-2);}
const int G=3,inv_G=inv(G);
inline void NTT(vector<int> &a,int lim,int opt=1)
{
    static int rev[N*2],inv_lim;
    for(int i=0;i<lim;++i)
    {
        rev[i]=rev[i>>1]>>1|((i&1)*lim>>1);
        if(i<rev[i]) swap(a[i],a[rev[i]]);
    }
    for(int len=1,gn;len<lim;len<<=1)
    {
        gn=quick_pow(opt==1?G:inv_G,(mod-1)/(len<<1));
        for(int i=0,temp;i<lim;i+=len<<1)
            for(int j=0,gp=1;j<len;++j,gp=1ll*gp*gn%mod)
            {
                temp=1ll*gp*a[i+j+len]%mod;
                a[i+j+len]=(a[i+j]-temp+mod)%mod;
                a[i+j]=(a[i+j]+temp)%mod; 
            }
    }
    if(opt==-1)
    {
        inv_lim=inv(lim);
        for(int i=0;i<lim;++i)
            a[i]=1ll*inv_lim*a[i]%mod;
    }
}
inline vector<int> poly_mul(vector<int> a,vector<int> b)
{
    int n=a.size(),m=b.size(),lim=1;
    for(;lim<n+m-1;lim<<=1);
    a.resize(lim),b.resize(lim);
    NTT(a,lim),NTT(b,lim);
    for(int i=0;i<lim;++i) a[i]=1ll*a[i]*b[i]%mod;
    NTT(a,lim,-1),a.resize(n+m-1);
    return a;
}
inline void poly_add(vector<int> &a,const vector<int> &b)
{
    if(a.size()<b.size()) a.resize(b.size());
    for(unsigned i=0;i<b.size();++i) add(a[i],b[i]);
}
int n,sumr;
vector<int> f[N+5][2];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
inline void merge(int u,int v)
{
    vector<int> ans[2];
    for(int i=0;i<2;++i) for(int j=0;j<2;++j)
        poly_add(ans[i^j],poly_mul(f[u][i],f[v][j]));
    f[u][0]=ans[0],f[u][1]=ans[1];
}
int main()
{
    read(n);
    if(n&1) return puts("No"),0;
    for(int i=1,r;i<=n;++i)
    {
        read(r),sumr+=r,f[i][0]={1};
        f[i][1].resize(r+1),f[i][1][r]=1;
        q.push({r+1,i});
    }
    if(sumr&1) return puts("No"),0;
    while(q.size()>1)
    {
        int u=q.top().second;q.pop();
        int v=q.top().second;q.pop();
        merge(u,v);
        if(f[u][0].size()>sumr/2 && f[u][0][sumr/2]>2)
            return puts("Yes"),0;
        q.push({max(f[u][0].size(),f[u][1].size()),u});
    }
    puts("No");
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 9ms
memory: 53192kb

input:

4
1 1 1 1

output:

Yes

result:

ok single line: 'Yes'

Test #2:

score: 0
Accepted
time: 3ms
memory: 52936kb

input:

6
1 3 1 3 1 3

output:

Yes

result:

ok single line: 'Yes'

Test #3:

score: 0
Accepted
time: 7ms
memory: 53824kb

input:

6
2 2 1 1 1 1

output:

No

result:

ok single line: 'No'

Test #4:

score: 0
Accepted
time: 3ms
memory: 54024kb

input:

8
99 98 15 10 10 5 2 1

output:

Yes

result:

ok single line: 'Yes'

Test #5:

score: -100
Time Limit Exceeded

input:

100
9384 9699 9434 9482 9525 39 26 9314 9610 9698 79 9558 9398 9358 9389 52 9395 286 9401 9449 9511 219 9291 9 9384 117 9344 98 9341 32 9375 8893 9414 9434 9412 9699 370 9363 9458 9639 9517 9347 9427 9357 9688 9456 9394 9455 9818 9436 9436 9228 9372 9345 9746 9540 9404 9475 9482 9535 9404 9400 28 91...

output:


result: