結果

問題 No.2672 Subset Xor Sum
ユーザー tour2st
提出日時 2024-03-15 21:49:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 353 ms / 2,000 ms
コード長 2,024 bytes
コンパイル時間 942 ms
コンパイル使用メモリ 97,872 KB
実行使用メモリ 325,164 KB
最終ジャッジ日時 2024-09-30 04:18:14
合計ジャッジ時間 6,717 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 66
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <random>
#include <time.h>
#include <map>
using namespace std;

int n,a[500000],sum;
//dp[flag][i][j] = 
//i個目まで見てxorがjであるようなとき
//aの要素の使用個数の最小値
//flag:1つ以上使ったか？
int dp[2][5010][1<<13];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        sum ^= a[i];
    }

    //すべてのxorが0出ないなら存在しない
    if(sum != 0)
    {
        cout << "No" << endl;
    }
    else
    {
        //5001個より多いなら鳩ノ巣原理より、一致するものが存在
        //よってYes
        if(n>5001)
        {
            cout << "Yes" << endl;
        }
        else
        {
            for(int i = 0; i <= n; i++)
            {
                for(int j = 0; j < (1<<13); j++)
                {
                    dp[0][i][j] = dp[1][i][j] = 100000;
                }
            }
            dp[0][0][0] = 0;
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < (1<<13); j++)
                {
                    if(dp[0][i][j]<100000)
                    {
                        //printf("[%d:%d]%d->%d\n",i,j,j,j^a[i]);
                        dp[0][i+1][j] = min(dp[0][i+1][j],dp[0][i][j]);
                        dp[1][i+1][j^a[i]] = min(dp[1][i+1][j^a[i]],dp[0][i][j]+1);
                    }
                    if(dp[1][i][j]<100000)
                    {
                        dp[1][i+1][j] = min(dp[1][i+1][j],dp[1][i][j]);
                        dp[1][i+1][j^a[i]] = min(dp[1][i+1][j^a[i]],dp[1][i][j]+1);
                    }
                }
            }
            if(dp[1][n][0]<n)
            {
                //cout << dp[1][n][0] << endl;
                cout << "Yes" << endl;
            }
            else
            {
                cout << "No" << endl;
            }
        }
    }
}
0