Submission #66388577

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define all(a) begin(a), end(a)
#define len(a) (int)((a).size())

const ll LG = 60, MX = (1ll << 60);
mt19937_64 rd(228);

struct sp {
    vector<ll> bt;
    sp() {
        bt.resize(LG, -1);
    }

    void ins(ll v) {
        for (int b = LG - 1; b >= 0; --b) {
            if (!((v >> b) & 1)) continue;
            if (bt[b] == -1) {
                bt[b] = v;
                return;
            }
            v ^= bt[b];
        }
    }

    void merge(const sp& a) {
        for (auto v : a.bt) ins(v);
    }

    bool find(ll v) {
        for (int b = LG - 1; b >= 0; --b) {
            if (!((v >> b) & 1)) continue;
            if (bt[b] == -1) return false;
            v ^= bt[b];
        }
        return true;
    }
};

vector<sp> spaces;
vector<ll> vec;
vector<ll> ops, bad = {-1};

void apply(int i) {
    assert(i + 1 < len(vec));
    ll x = vec[i] ^ vec[i + 1];
    vec[i] = x;
    vec[i + 1] = x;
    ops.push_back(i);
}

set<array<ll, 3>> vis;
bool dfs(int i, ll k) {
    if (i > len(vec) || len(ops) >= 10'000) return false;
    if (i == len(vec)) {
        if (k == 0) {
            return true;
        } else {
            return false;
        }
    }
    if (vis.count({i, vec[i], k})) return false;
    vis.insert({i, vec[i], k});
    if (vec[i] == k) {
        return true;
    }
    if (i == len(vec)) return false;

    if (dfs(i + 1, k ^ vec[i])) {
        apply(i);
        return true;
    }
    
    for (int t = 2; ; ++t) {
        ops.push_back(i + t - 2);
        ops.push_back(i + t - 2);
        if (i + t <= len(vec)) {
            if (i + t == len(vec)) {
                if (dfs(i + t, k)) {
                    for (int j = i; j < i + t; ++j) vec[j] = 0;
                    return true;
                }
            } else {
                if (dfs(i + t + 1, k ^ vec[i + t])) {
                    for (int j = i; j < i + t; ++j) vec[j] = 0;
                    for (int j = i + t - 1; j >= i; --j) {
                        apply(j);
                    }
                    return true;
                }
            }
        } else {
            for (int j = 2; j <= t; ++j) {
                ops.pop_back(); ops.pop_back();
            }
            return false;
        }
    }

    return false;
}

void solve() {
    ll n, k;
    cin >> n >> k;
    //n = 30;
    //k = rd() % MX;
    vec.resize(n);
    for (auto &c : vec) {
        cin >> c;
        //c = rd() % MX;
    }
    vis.clear();

    // spaces.clear();
    // spaces.resize(n + 1);
    // spaces[n - 1].ins(vec.back());
    // for (int i = n - 2; i >= 0; --i) {
    //     spaces[i].merge(spaces[i + 2]);
    //     if (i + 3 <= n) spaces[i].merge(spaces[i + 3]);
    //     for (auto v : spaces[i + 1].bt) {
    //         spaces[i].ins(v ^ vec[i]);
    //     }
    //     spaces[i].ins(vec[i]);
    // }

    ops.clear();
    if (dfs(0, k)) {
        cout << "Yes\n";
        assert(vec[0] == k);
        cout << len(ops) << "\n";
        for (auto c : ops) cout << c + 1 << " ";
        cout << "\n";
    } else {
        cout << "No\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
} 

Submission Info

Judge Result