結果
問題 | No.2672 Subset Xor Sum |
ユーザー |
![]() |
提出日時 | 2024-03-15 22:15:25 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 171 ms / 2,000 ms |
コード長 | 9,314 bytes |
コンパイル時間 | 5,092 ms |
コンパイル使用メモリ | 328,288 KB |
実行使用メモリ | 165,248 KB |
最終ジャッジ日時 | 2024-09-30 04:22:49 |
合計ジャッジ時間 | 11,680 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 66 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;#define rep(i,t,n) for(long long i=t;i<n;i++)#define rep2(i,A) for(auto &i:A)#define Sort(a) sort(a.begin(),a.end())#define rSort(a,n,m) sort(a.begin()+n,a.begin()+m+1)#define Reverse(a) reverse(a.begin(),a.end())#define rReverse(a,n,m) reverse(a.begin()+n,a.begin()+m+1)#define MOD1 998244353#define MOD2 1000000007#define sign(i) -1*pow(-1,i)#define vi(A,N,i) vector<long long> A(N,i)#define vd(A,N,i) vector<double> A(N,i)#define vc(A,N,i) vector<char> A(N,i)#define vs(A,N,i) vector<string> A(N,i)#define vb(A,N,i) vector<bool> A(N,i)#define vp(A,N,i) vector<Pair> A(N,{i,i})#define vvi(A,N,M,i) vector<vector<long long>> A(N,vector<long long>(M,i))#define vvd(A,N,M,i) vector<vector<double>> A(N,vector<double>(M,i))#define vvc(A,N,M,i) vector<vector<char>> A(N,vector<char>(M,i))#define vvb(A,N,M,i) vector<vector<bool>> A(N,vector<bool>(M,i))#define vvvi(A,N,M,L,i) vector<vector<vector<ll>>> A(N,vector<vector<ll>>(M,vector<ll>(L,i)))#define ll long long#define INF ((1LL<<62)-(1LL<<31))#define ALL(a) (a).begin(),(a).end()//((a+b+c)-max(a,max(b,c))-min(a,min(b,c)))//cout << fixed << setprecision(桁数);using VVi=vector<vector<ll>>;using Pair=pair<ll,ll>;using graphi=vector<vector<ll>>;using graphp=vector<vector<Pair>>;struct Plane{ll x;ll y;};struct Path{ll cost;ll to;};template<typename T>void CIN(vector<T> &A){rep(i,0,(ll)A.size()){cin>>A[i];}return;}struct ThreePlane{ll x,y,z;ThreePlane(ll X=0,ll Y=0,ll Z=0):x(X),y(Y),z(Z){}bool operator<(const ThreePlane& other) const {return x<other.x;}bool operator<=(const ThreePlane& other) const {return x<=other.x;}bool operator>(const ThreePlane& other) const {return x>other.x;}bool operator>=(const ThreePlane& other) const {return x>=other.x;}};struct FourPlane{ll dist;ll x;ll y;ll stat;};struct Fraction{ll p,q,r;Fraction(ll P = 0, ll Q = 1,ll R = 1): p(P), q(Q),r(R){}bool operator<(const Fraction &other)const{if(p*other.q != other.p*q){return p*other.q < other.p*q;}else{return r>other.r;}}};struct Matrix{//正方のみvector<vector<ll>> mat;Matrix(ll size):mat(vector<vector<ll>>(size,vector<ll>(size,0))){}void showerr(){rep2(i,mat){rep2(j,i)cerr<<j<<" ";cerr<<endl;}return;}void showout(){rep2(i,mat){rep2(j,i)cout<<j<<" ";cout<<endl;}return;}};template<typename T>struct Zaatu{bool sorted;vector<T> za;Zaatu():sorted(false){}void add(T x){za.push_back(x);sorted=false;}void build(){sort(std::begin(za),std::end(za));sorted=true;za.erase(unique(std::begin(za),std::end(za)),std::end(za));}ll size(){if(!sorted)build();return (ll)za.size();}const T &operator[](int i){if(!sorted)build();return za[i];}ll get(const T &x){//x以上の最小値のindexif(!sorted)build();return lower_bound(std::begin(za),std::end(za),x)-std::begin(za);}vector<ll> get(vector<T> mo){if(!sorted)build();vector<ll> result;transform(std::begin(mo),std::end(mo),back_inserter(result),[&](const T &x){return lower_bound(std::begin(za),std::end(za),x)-std::begin(za);});return result;}typename vector<T>::iterator begin(){if(!sorted)build();return std::begin(za);}typename vector<T>::iterator end(){if(!sorted)build();return std::end(za);}};ll POW(ll a,ll b,ll mod){ll c=1;a%=mod;while(b!=0){if(b%2){c*=a;c%=mod;}a*=a;a%=mod;b/=2;}return c;}ll GCD(ll a,ll b){if(b==0)return a;return GCD(b,a%b);}pair<long long, long long> extGCD(long long a, long long b) {// ax+by=1 solverif (b == 0) return make_pair(1, 0);long long x,y;tie(y,x)=extGCD(b,a%b);y-=a/b*x;return make_pair(x,y);}ll SQRT(ll a){ll low,high,mid;low=0;high=1LL<<31;while(high-low!=1){mid=(low+high)/2;if(mid*mid<=a){low=mid;}else{high=mid;}}return low;}string strmin(string x,string y){ll minlength=min((int)x.size(),(int)y.size());rep(i,0,minlength){if(x[i]>y[i])return y;if(x[i]<y[i])return x;}if((int)x.size()>(int)y.size())return y;return x;}ll LCS(string x,string y){ll xsize=(ll)x.size();ll ysize=(ll)y.size();vvi(dp,xsize+1,ysize+1,0);rep(i,1,xsize+1){rep(j,1,ysize+1){if(x[i-1]==y[j-1])dp[i][j]=max(max(dp[i-1][j-1]+1,dp[i][j-1]),dp[i-1][j]);else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);}}return dp[xsize][ysize];}ll Factorial(ll n,ll mod){ll a=1;if(n>=mod)return 0;rep(i,1,n+1){a*=i;a%=mod;}return a;}ll Combination(ll n,ll k,ll mod){if(n<k)return 0;ll a=Factorial(n,mod);ll b=inv_mod(Factorial(k,mod),mod);ll c=inv_mod(Factorial(n-k,mod),mod);a*=b;a%=mod;a*=c;a%=mod;return a;}vector<pair<char,long long>> RLE(string x,char s=' ',long long a=0,vector<pair<char,long long>> res={}){for(auto i:x){if(s==i){a++;}else{if(s!=' ')res.push_back({s,a});s=i,a=1;}}res.push_back({s,a});return res;}vector<ll> cu1d(vector<ll> A){ll cu1=A.size();vector<ll> res(cu1+1,0);rep(i,0,cu1)res[i+1]=A[i];rep(i,1,cu1+1)res[i]+=res[i-1];return res;}vector<vector<ll>> cu2d(vector<vector<ll>> A){ll cu1=A.size(),cu2=A[0].size();vector<vector<ll>> res(cu1+1,vector<ll>(cu2+1,0));rep(i,0,cu1)rep(j,0,cu2)res[i+1][j+1]=A[i][j];rep(i,1,cu1+1)rep(j,0,cu2+1)res[i][j]+=res[i-1][j];rep(j,0,cu1+1)rep(i,1,cu2+1)res[j][i]+=res[j][i-1];return res;}ll LIS(vector<ll> A){ll a=(ll)A.size();vector<ll> result(a,INF);ll answer=0;rep(i,0,a){ll ok=-1;ll ng=a;while(ng-ok!=1){ll mid=(ok+ng)/2;if(A[i]<=result[mid])ng=mid;else ok=mid;}result[ok+1]=A[i];answer=max(answer,ok+2);}return answer;}vector<ll> zaatu(vector<ll> A){vector<ll> B=A;Sort(B);B.erase(unique(ALL(B)),end(B));vector<ll> res;transform(ALL(A),back_inserter(res),[&](const ll &x){return lower_bound(ALL(B),x)-begin(B);});return res;}vector<string> trim(vector<string> A){bool frag=0;char s='#';ll h=(ll)A.size();ll w=(ll)A[0].size();ll a=-1,b=h,c=-1,d=w;for(ll i=0;i<h;i++){for(ll j=0;j<w;j++)if(A[i][j]==s)frag=1;if(frag)break;a=i;}frag=0;for(ll i=h-1;i>=0;i--){for(ll j=0;j<w;j++)if(A[i][j]==s)frag=1;if(frag)break;b=i;}frag=0;for(ll i=0;i<w;i++){for(ll j=0;j<h;j++)if(A[j][i]==s)frag=1;if(frag)break;c=i;}frag=0;for(ll i=w-1;i>=0;i--){for(ll j=0;j<h;j++)if(A[j][i]==s)frag=1;if(frag)break;d=i;}vector<string> B(b-a-1,"");for(ll i=a+1;i<b;i++)for(ll j=c+1;j<d;j++)B[i-a-1]+=A[i][j];return B;}char to_upper(char s){if('a'<=s){s-=32;}return s;}char to_lower(char s){if(s<='Z'){s+=32;}return s;}vector<vector<ll>> Warshall(vector<vector<ll>> A){ll a=A.size();rep(k,0,a)rep(i,0,a)rep(j,0,a)A[i][j]=min(A[i][j],A[i][k]+A[k][j]);return A;}//Warshall rep(k,0,a)rep(i,0,a)rep(j,0,a)A[i][j]=min(A[i][j],A[i][k]+A[k][j]);long long a,b,c,d,e,f,g,h,ans=0;string w,x="",y="",z="";char s,t,u;bool frag=false,frag1=false,frag2=false;vector<ll> X={1,0,-1,0},Y={0,1,0,-1};bool dp[5050][8192][4]={};// vvvi(dp,5050,8192,2,0);int main(){cin>>a;vi(A,a,0);CIN(A);rep(i,0,a)ans^=A[i];vi(B,5050,0);rep(i,0,a)B[A[i]]++;if(ans){cout<<"No"<<endl;return 0;}if(B[0]==0){dp[0][0][0]=1;}else if(B[0]==1){dp[0][0][0]=1;dp[0][0][1]=1;dp[0][0][2]=1;}else{dp[0][0][0]=1;dp[0][0][1]=1;dp[0][0][2]=1;dp[0][0][3]=1;}if(B[0]!=0)dp[0][0][1]=1;rep(i,1,5050){rep(j,0,8192){if(B[i]==0){dp[i][j][0]|=dp[i-1][j][0];dp[i][j][1]|=dp[i-1][j][1];dp[i][j][2]|=dp[i-1][j][2];dp[i][j][3]|=dp[i-1][j][3];}else if(B[i]==1){if((j^i)<8192)dp[i][j^i][2]|=dp[i-1][j][0];if((j^i)<8192)dp[i][j^i][3]|=dp[i-1][j][1];if((j^i)<8192)dp[i][j^i][2]|=dp[i-1][j][2];if((j^i)<8192)dp[i][j^i][3]|=dp[i-1][j][3];dp[i][j][1]|=dp[i-1][j][0];dp[i][j][1]|=dp[i-1][j][1];dp[i][j][3]|=dp[i-1][j][2];dp[i][j][3]|=dp[i-1][j][3];}else{if((j^i)<8192)dp[i][j^i][2]|=dp[i-1][j][0];if((j^i)<8192)dp[i][j^i][3]|=dp[i-1][j][1];if((j^i)<8192)dp[i][j^i][2]|=dp[i-1][j][2];if((j^i)<8192)dp[i][j^i][3]|=dp[i-1][j][3];dp[i][j][1]|=dp[i-1][j][0];dp[i][j][1]|=dp[i-1][j][1];dp[i][j][3]|=dp[i-1][j][2];dp[i][j][3]|=dp[i-1][j][3];dp[i][j][1]|=dp[i-1][j][0];dp[i][j][1]|=dp[i-1][j][1];dp[i][j][3]|=dp[i-1][j][2];dp[i][j][3]|=dp[i-1][j][3];dp[i][j][2]|=dp[i-1][j][0];dp[i][j][3]|=dp[i-1][j][1];dp[i][j][2]|=dp[i-1][j][2];dp[i][j][3]|=dp[i-1][j][3];}}// cerr<<0;if(dp[i][0][3]){cout<<"Yes"<<endl;return 0;}}// rep(i,0,12){// rep(j,0,12)cerr<<dp[i][j][1]<<" ";// cerr<<endl;// }if(dp[5040][0][3])cout<<"Yes"<<endl;else cout<<"No"<<endl;}