#960864 (C++17) No.2672 Subset Xor Sum

提出ソース

結果

問題	No.2672 Subset Xor Sum
ユーザー	GEX777
提出日時	2024-03-15 23:09:57
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	15,781 bytes
コンパイル時間	1,548 ms
コンパイル使用メモリ	155,072 KB
実行使用メモリ	13,636 KB
最終ジャッジ日時	2024-09-30 02:44:18
合計ジャッジ時間	5,776 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,636 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	2 ms 6,824 KB
testcase_06	AC	1 ms 6,816 KB
testcase_07	AC	2 ms 6,816 KB
testcase_08	AC	2 ms 6,820 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	2 ms 6,816 KB
testcase_13	AC	2 ms 6,820 KB
testcase_14	AC	2 ms 6,820 KB
testcase_15	AC	2 ms 6,820 KB
testcase_16	AC	1 ms 6,820 KB
testcase_17	AC	2 ms 6,816 KB
testcase_18	AC	2 ms 6,820 KB
testcase_19	AC	1 ms 6,816 KB
testcase_20	AC	2 ms 6,820 KB
testcase_21	AC	2 ms 6,816 KB
testcase_22	AC	2 ms 6,820 KB
testcase_23	AC	2 ms 6,820 KB
testcase_24	AC	2 ms 6,816 KB
testcase_25	AC	2 ms 6,816 KB
testcase_26	AC	6 ms 6,816 KB
testcase_27	AC	7 ms 6,816 KB
testcase_28	AC	1 ms 6,816 KB
testcase_29	AC	2 ms 6,820 KB
testcase_30	AC	2 ms 6,820 KB
testcase_31	TLE	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-
testcase_45	--	-
testcase_46	--	-
testcase_47	--	-
testcase_48	--	-
testcase_49	--	-
testcase_50	--	-
testcase_51	--	-
testcase_52	--	-
testcase_53	--	-
testcase_54	--	-
testcase_55	--	-
testcase_56	--	-
testcase_57	--	-
testcase_58	--	-
testcase_59	--	-
testcase_60	--	-
testcase_61	--	-
testcase_62	--	-
testcase_63	--	-
testcase_64	--	-
testcase_65	--	-
testcase_66	--	-
testcase_67	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

/**
 * @file template.cpp
 * @brief 競技プログラミングのデッキ
 * @author Gex777
 * @date update:2024/03/10
 */

#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <valarray>
#include <vector>
#include <functional>
// #include <atcoder/all> //ACL

using namespace std;
// using namespace atcoder;

// 独自型定義
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

// マクロの宣言
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), e.rend()

// 定数宣言
constexpr double PI = 3.141592653589793;
constexpr ll MOD998 = 998244353;
constexpr ll MOD107 = 1000000007;

/****************************************************
*************ここから下は自作ライブラリ**************
****************************************************/

// コンテナの中身を表示, 1行で出力をする, debug用
template <typename T>
void printv(T &a)
{
    for (const auto &x : a)
    {
        cout << x << " ";
    }
    puts("");
    return;
}

// コンテナの中身を表示, 二次元配列用
template <typename T>
void printvv(T &a)
{
    for (const auto &x : a)
    {
        printv(x);
    }
}

// コンテナの中身を表示, pair型
template <typename T>
void print_vpair(const T &a)
{
    for (const auto &x : a)
    {
        cout << "(" << x.first << ", " << x.second << "), ";
    }
    puts("");
    return;
}

template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}

template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}

// コンテナの中身を表示, 改行して出力をする, debug用
template <typename T>
void println(T &a)
{
    for (const auto &x : a)
    {
        cout << x << endl;
    }
    return;
}

// 1~Nまでの総和を求める
ll sum_from_1_to_N(ll N)
{
    if (N < 1LL)
    {
        return 0;
    }

    if ((N & 1) == 0) // even
    {
        return N / 2 * (N + 1);
    }
    else // odd
    {
        return (N + 1) / 2 * N;
    }
}

// A+1~Nまでの総和を求める
ll sum_from_A_to_B(ll A, ll B)
{
    return sum_from_1_to_N(B) - sum_from_1_to_N(A);
}

// a^bを求める, 繰り返し2乗法を用いる,3番目の引数はModを取る場合に設定
ll intPowMod(ll a, ll b, const ll MOD = LLONG_MAX)
{
    ll ans = 1;
    ll A = a;
    while (b > 0)
    {
        int n = b % 2;
        b /= 2;

        if (n == 1)
        {
            ans *= A % MOD;
            ans %= MOD;
        }
        A = ((A % MOD) * (A % MOD)) % MOD;
    }
    return ans;
}

ld arg_to_rad(ld arg) { return (arg * PI / 180.0); }

ld rad_to_arg(ld rad) { return rad * 180.0 / PI; }

// C(n, m)を求める
ll combination(const ll n, const ll m)
{
    assert(n >= m); // n>=mは保証される

    ll up = 1;
    ll down = 1;
    for (int i = n; i > n - m; i--)
    {
        up *= i;
    }

    for (int i = m; i >= 2; i--)
    {
        down *= i;
    }

    return up / down;
}

// 動的計画法で前処理,O(N**2)
vvll combination_table(const int MAX_N = 50)
{
    vvll com = vvll(MAX_N + 1, vll(MAX_N + 1, 0)); // 前計算の結果を保存
    com[0][0] = 1;
    for (int i = 1; i <= MAX_N; ++i)
    {
        com[i][0] = 1;
        for (int j = 1; j <= MAX_N; j++)
        {
            com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]);
        }
    }
    return com;
}

// a÷bをMODで割ったあまりを返す関数
ll DivisionMod(ll a, ll b, ll MOD)
{
    return (a * intPowMod(b, MOD - 2, MOD)) % MOD;
}

// C(n, r)をModで割った余りを返す関数, 3番めの引数を入れないと通常のConbination
ll combinationMod(ll n, ll r, ll MOD = LLONG_MAX)
{
    // 分子upを求める
    ll up = 1;
    for (ll i = n - r + 1; i <= n; ++i)
    {
        up = (up * i) % MOD;
    }

    // 分母downを求める
    ll down = 1;
    for (ll i = 1; i <= r; ++i)
        down = (down * i) % MOD;

    return DivisionMod(up, down, MOD);
}

// a,bの最大公約数を求める, A>=B>=0の時, 計算量O(logB)
long long GCD(long long a, long long b)
{
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}

// 拡張ユークリッドの互助法, 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long &x, long long &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

// 最小公倍数
ll LCM(ll a, ll b) { return a * b / GCD(a, b); }

// 素数判定, P->true, not_P->false
bool check_Prime(ll N)
{
    if (N == 2)
        return true;

    if (N == 1 || (N & 1) == 0)
        return false;

    for (ll i = 3; i <= sqrt(N); i += 2)
    {
        if (N % i == 0)
            return false;
    }
    return true;
}

// 素因数分解,key:素数, value:指数のmap<ll,ll>を返す
map<ll, ll> prime_factorize(ll number)
{
    if (number == 1)
    {
        return {{1LL, 1LL}};
    }

    map<ll, ll> table;

    for (ll i = 2; i * i <= number; ++i)
    {
        while (number % i == 0)
        {
            table[i]++;
            number /= i;
        }
    }

    if (number != 1LL)
    {
        table[number]++;
    }
    return table;
}

// Eratosthenesのtableを使った素因数分解
vector<pii> prime_factorize(ll number, const vi &IsPrime)
{
    if (number == 1)
    {
        return {{1, 1}};
    }

    vector<pii> factor;
    while (number != 1)
    {
        int cnt = 0;
        int f = IsPrime[number];

        while (IsPrime[number] == f)
        {
            number /= IsPrime[number];
            ++cnt;
        }

        factor.push_back({f, cnt});
    }
    return factor;
}

/* エラストステネス and 高速素因数分解
   prime->IsPrime[i]=i; not prime ->最小の素因数
   高速素因数分解をするのにはprime_factorize(ll num, ll table)を使う */
vi Eratosthenes(size_t max_number)
{
    vi IsPrime(max_number + 1);

    // tableの初期化
    for (int i = 1; i < IsPrime.size(); ++i)
    {
        IsPrime[i] = i;
    }

    for (int i = 2; i <= sqrt(max_number); ++i)
    {
        for (int j = i; j <= max_number; j += i)
        {
            if (IsPrime[j] == j)
            {
                IsPrime[j] = i;
            }
        }
    }
    return IsPrime;
}

// O(N)でNの階乗を求める
ll factorial(const ll N)
{
    ll ans = 1;
    for (ll i = 1; i <= N; ++i)
    {
        ans *= i;
    }
    return ans;
}

// Run Length Encoding, ランレングス圧縮
template <typename T>
vector<pair<T, int>> RLE(const vector<T> &A)
{
    vector<pair<T, int>> rle;
    rle.push_back({A.front(), 1});

    for (int i = 1; i < A.size(); ++i)
    {
        if (rle.back().first == A[i])
        {
            rle.back().second++;
        }
        else
        {
            rle.push_back({A[i], 1});
        }
    }
    return rle;
}

vector<pair<char, int>> RLE(const string &S)
{
    vector<pair<char, int>> rle;
    rle.push_back({S.front(), 1});

    for (int i = 1; i < S.size(); ++i)
    {
        if (rle.back().first == S[i])
        {
            rle.back().second++;
        }
        else
        {
            rle.push_back({S[i], 1});
        }
    }
    return rle;
}

void DEBUG_INDICATE()
{
    static int cnt = 0;
    cout << "-----DEBUG:" << cnt++ << "------" << endl;
    return;
}

// 正方行列の回転を行うライブラリ
template <typename T>
struct ROTATE
{
    static vector<vector<T>> clockwise(const vector<vector<T>> &X)
    {
        assert(X.size() == X[0].size());
        const int N = X.size();
        vector<vector<T>> Y(N, vector<T>(N));

        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                Y[j][N - 1 - i] = X[i][j];
        return Y;
    }

    static vector<vector<T>> anticlockwise(const vector<vector<T>> &X)
    {
        assert(X.size() == X[0].size());
        const int N = X.size();
        vector<vector<T>> Y(N, vector<T>(N));

        for (int i = 0; i < N; ++i)
            for (int j = N - 1; 0 <= j; --j)
                Y[N - 1 - j][i] = X[i][j];
        return Y;
    }
};

/* RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
    update(i,x): i 番目の要素を x に更新。O(log(n))
    query(a,b): [a,b) での最小の要素を取得。O(log(n))
*/
template <typename T>
struct RangeMinimumQuery
{
    const T INF = numeric_limits<T>::max();
    int n;         // 葉の数
    vector<T> dat; // 完全二分木の配列
    RangeMinimumQuery(int n_) : n(), dat(n_ * 4, INF)
    { // 葉の数は 2^x の形
        int x = 1;
        while (n_ > x)
        {
            x *= 2;
        }
        n = x;
    }
    void update(int i, T x)
    {
        i += n - 1;
        dat[i] = x;
        while (i > 0)
        {
            i = (i - 1) / 2; // parent
            dat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }
    // the minimum element of [a,b)
    T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
    T query_sub(int a, int b, int k, int l, int r)
    {
        if (r <= a || b <= l)
        {
            return INF;
        }
        else if (a <= l && r <= b)
        {
            return dat[k];
        }
        else
        {
            T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return min(vl, vr);
        }
    }
};

// 1次元累積和のためのクラス
template <typename T>
struct CSUM1D
{
    vector<T> csum;
    // 1次元累積和にするコンストラクタ
    CSUM1D(const vector<T> &_csum)
    {
        const size_t N = _csum.size();
        csum = vll(N + 1, 0);
        for (int i = 0; i < N; ++i)
            csum[i + 1] = csum[i] + _csum[i];
    }

    // 区間[L,R]の合計値(閉区間)
    T get(const int L, const int R)
    {
        const size_t N = csum.size();
        assert(1 <= L && L <= R && R <= N);
        return csum[R] - csum[L-1];
    }
};

// 二次元累積和のためのクラス
template <typename T>
struct CSUM2D
{
    vector<vector<T>> csum;
    // 二次元累積和にするコンストラクタ
    CSUM2D(const vector<vector<T>> &_csum)
    {
        const int N = _csum.size();
        const int M = _csum[0].size();
        csum = vector<vector<T>>(N + 1, vector<T>(M + 1, 0));

        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= M; ++j)
                csum[i][j] = _csum[i - 1][j - 1];

        for (int i = 0; i <= N; ++i)
            for (int j = 0; j < M; ++j)
                csum[i][j + 1] = csum[i][j] + csum[i][j + 1];

        for (int j = 0; j <= M; ++j)
            for (int i = 0; i < N; ++i)
                csum[i + 1][j] = csum[i][j] + csum[i + 1][j];
    }

    //(i1,j1)を左上,(i2,j2)を右下とする長方形領域の合計値(閉区間)
    T get(const int i1, const int j1, const int i2, const int j2)
    {
        assert(i1 <= i2 && j1 <= j2);
        assert(1 <= i1 && i1 < csum.size() && 1 <= j1 && j1 < csum[0].size());
        assert(1 <= i2 && i2 < csum.size() && 1 <= j2 && j2 < csum[0].size());
        T s4 = csum[i2][j2];
        T s1 = csum[i1 - 1][j1 - 1];
        T s2 = csum[i1 - 1][j2];
        T s3 = csum[i2][j1 - 1];
        return s4 - s3 - s2 + s1;
    }
};

/**
 * @brief 要素数N,二項演算op, 初期値INFを指定するセグ木
 * update(i,x): i 番目の要素を x に更新。O(log(n))
 * query(a,b): [a,b) での最小の要素を取得。O(log(n))
 */
template <typename T>
struct SegTree
{
    T INF;                // 初期値
    int N;                // 葉の数
    vector<T> data;       // 完全二分木の配列
    function<T(T, T)> op; // 二項演算

    SegTree(int _N, const function<T(T, T)> _op, const T _INF) : N(), data(_N * 4, _INF), op(_op), INF(_INF)
    { // 葉の数は 2^x の形
        int x = 1;
        while (_N > x)
        {
            x *= 2;
        }
        N = x;
    }
    void update(int i, T x)
    {
        i += N - 1;
        data[i] = x;
        while (i > 0)
        {
            i = (i - 1) / 2; // parent
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }

    // the minimum element of [a,b)
    T query(int a, int b) { return query_sub(a, b, 0, 0, N); }
    T query_sub(int a, int b, int k, int l, int r)
    {
        if (r <= a || b <= l)
        {
            return INF;
        }
        else if (a <= l && r <= b)
        {
            return data[k];
        }
        else
        {
            T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return op(vl, vr);
        }
    }

    // 添字でアクセス
    T operator[](int i)
    {
        return data[i + N - 1];
    }
};

// Union-Find
struct UnionFind
{
    vector<int> par, rank, siz;

    // 構造体の初期化
    UnionFind(int n) : par(n, -1), rank(n, 0), siz(n, 1) {}

    // 根を求める
    int root(int x)
    {
        if (par[x] == -1)
            return x; // x が根の場合は x を返す
        else
            return par[x] = root(par[x]); // 経路圧縮
    }

    // x と y が同じグループに属するか (= 根が一致するか)
    bool issame(int x, int y) { return root(x) == root(y); }

    // x を含むグループと y を含むグループを併合する
    bool unite(int x, int y)
    {
        int rx = root(x), ry = root(y); // x 側と y 側の根を取得する
        if (rx == ry)
            return false; // すでに同じグループのときは何もしない
        // union by rank
        if (rank[rx] < rank[ry])
            swap(rx, ry); // ry 側の rank が小さくなるようにする
        par[ry] = rx;     // ry を rx の子とする
        if (rank[rx] == rank[ry])
            rank[rx]++;     // rx 側の rank を調整する
        siz[rx] += siz[ry]; // rx 側の siz を調整する
        return true;
    }

    // x を含む根付き木のサイズを求める
    int size(int x) { return siz[root(x)]; }
};

/*********************************************
*************ライブラリ終わり******************
***********************************************/

int main()
{
    int N;
    cin >> N;

    const int L = 1<<13;
    vb dp(L,false);
    dp[0] = true;

    int sum = 0;
    bool is_ok = false;
    for(int i=0; i<N; ++i)
    {
        // cout << "i=" << i << ": ";
        // printv(dp);
        vb dp2 = dp;
        int A;
        cin >> A;
        sum ^= A;

        for(int S=0; S<L; ++S)
        {
            if(dp[S])
            {
                dp2[S^A] = true;
                // cout << "S^A= " << (S^A) << endl; 
                if((S^A)==0 && i < N-1)
                {
                    is_ok = true;
                }
            }
            
        }

        swap(dp, dp2);
    }
    //  cout << "i=" << N << ": ";
    // printv(dp);

    // cout << "sum=" << sum << endl;
    cout << ((is_ok && sum == 0)?"Yes":"No") << endl;

}

yukicoder

結果

テストケース

ソースコード