QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#188924 | #5475. Make a Loop | Bird | TL | 3ms | 30680kb | C++14 | 3.5kb | 2023-09-26 16:51:38 | 2023-09-26 16:51:38 |
Judging History
answer
#include<bits/stdc++.h>
#define N 500000
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 29300kb
input:
4 1 1 1 1
output:
Yes
result:
ok single line: 'Yes'
Test #2:
score: 0
Accepted
time: 3ms
memory: 29972kb
input:
6 1 3 1 3 1 3
output:
Yes
result:
ok single line: 'Yes'
Test #3:
score: 0
Accepted
time: 3ms
memory: 30680kb
input:
6 2 2 1 1 1 1
output:
No
result:
ok single line: 'No'
Test #4:
score: 0
Accepted
time: 0ms
memory: 30396kb
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...