#960401 (C++23) No.2672 Subset Xor Sum

提出ソース
結果

問題	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
権限があれば一括ダウンロードができます
ソースコード

raw source code
#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以上の最小値のindex
    if(!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 solver
  if (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;
}
yukicoder

結果

ソースコード
