Submission #66388328

Source Code Expand

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

const ll MAX_BIT = 60;
void solve() {
    ll n, k;
    cin >> n >> k;
    vector<ll> arr(n);
    for (auto &x : arr) cin >> x;

    ll odd_xor = 0, even_xor = 0;
    unsigned long long odd_mask = 0ULL, even_mask = 0ULL;
    for (int i = 0; i < n; ++i) {
        if ((i % 2) == 0) {
            odd_xor ^= arr[i];
            odd_mask |= (1ULL << i);
        } else {
            even_xor ^= arr[i];
            even_mask |= (1ULL << i);
        }
    }

    vector<ll> basis_val(MAX_BIT + 1, 0LL);
    vector<unsigned long long> basis_mask(MAX_BIT + 1, 0ULL);
    vector<unsigned long long> null_masks;

    auto insert_basis = [&](ll x, unsigned long long m) {
        for (int b = MAX_BIT; b >= 0; --b) {
            if (((x >> b) & 1) == 0) continue;

            if (basis_val[b] == 0) {
                basis_val[b]  = x;
                basis_mask[b] = m;
                return;
            }

            x ^= basis_val[b];
            m ^= basis_mask[b];
        }
        null_masks.push_back(m);
    };

    for (int i = 0; i < n; ++i) {
        insert_basis(arr[i], (1ULL << i));
    }

    auto make_k_mask = [&](ll target) -> unsigned long long {
        ll x = target;
        unsigned long long m = 0ULL;
        for (int b = MAX_BIT; b >= 0; --b) {
            if (((x >> b) & 1) == 0) continue;
            if (basis_val[b] == 0) {
                // b 비트를 제거할 기저가 없으면 불가능
                return (unsigned long long)(-1);
            }
            x ^= basis_val[b];
            m ^= basis_mask[b];
        }
        return (x == 0 ? m : (unsigned long long)(-1));
    };

    unsigned long long sol_mask = make_k_mask(k);
    if (sol_mask == (unsigned long long)(-1)) {
        cout << "No" << endl;
        return;
    }

    bool found = false;
    if (sol_mask != odd_mask && sol_mask != even_mask) {
        found = true;
    }

    unsigned long long final_mask = 0ULL;
    if(found){
        final_mask = sol_mask;
    } else{
        for (auto &v : null_masks) {
            unsigned long long t = sol_mask ^ v;
            if (t != odd_mask && t != even_mask) {
                found = true;
                final_mask = t;
                break;
            }
        }
        if (!found) {
            int z = null_masks.size();
            for (int i = 0; i < z && !found; ++i) {
                for (int j = i + 1; j < z && !found; ++j) {
                    unsigned long long v = null_masks[i] ^ null_masks[j];
                    unsigned long long t = sol_mask ^ v;
                    if (t != odd_mask && t != even_mask) {
                        found = true;
                        final_mask = t;
                        break;
                    }
                }
            }
        }
    }

    if (!found) {
        cout << "No" << endl;
        return;
    }

    cout << "Yes" << endl;
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
        if ((final_mask >> i) & 1ULL) {
            ans[i] = 1;
        }
    }
//    cout << ans.size() << endl;
//    for (int idx : ans) cout << idx << " ";
//    cout << endl;

    // 실제 조합으로 ans 만들기
    vector<int> res;
    int chk = 0;
    while(ans[chk] != ans[chk+1])
        chk++;

    if(ans[chk] == 0){
        res.push_back(chk);
        res.push_back(chk);
        for(int i = chk+2; i < n; i++){
            if(ans[i] == 0) {
                res.push_back(i-1);
                res.push_back(i-1);
            } else {
                // i부터 chk까지 res에 추가해주기
                // 그다음 chk+1부터 i-1까지 청소
                for(int j = i-1; j >= chk; j--)
                    res.push_back(j);

                for(int j = chk+1; j <= i-1; j++){
                    res.push_back(j);
                    res.push_back(j);
                }
            }
        }
    } else {
        int chk2 = chk + 2;
        while(chk2 < n && ans[chk2] == 1) {
            chk2++;
        }
        // chk2 - 1까지 모든 원소를 다 합쳐야 함
        for(int j = chk2 - 2; j >= chk; j--)
            res.push_back(j);

        // chk+1부터 chk2-2까지 청소
        for(int j = chk+1; j <= chk2 - 2; j++) {
            res.push_back(j);
            res.push_back(j);
        }
        // chk2 뒤쪽 원소들 넣어주기
        for(int i = chk2; i < n; i++){
            if(ans[i] == 0) {
                res.push_back(i-1);
                res.push_back(i-1);
            } else {
                // i부터 chk까지 res에 추가해주기
                // 그다음 chk+1부터 i-1까지 청소
                for(int j = i-1; j >= chk; j--)
                    res.push_back(j);

                for(int j = chk+1; j <= i-1; j++){
                    res.push_back(j);
                    res.push_back(j);
                }
            }
        }
    }

    if(chk != 0){
        // chk 앞쪽 원소들도 다 합쳐줘야 함
        if(ans[chk-1] == 0){
            if(chk == n-2){
                // 이때는 맨뒤가 11이라 지워줘야 함
                res.push_back(chk-1);
                res.push_back(chk-1);
            } else{
                // 이때는 맨뒤가 10임
                res.push_back(chk);
                res.push_back(chk-1);
                res.push_back(chk-1);
            }
        } else {
            res.push_back(chk-1);
            res.push_back(chk);
            res.push_back(chk-1);
            res.push_back(chk-1);
        }

        // chk+1에 모든 숫자 모을거임
        for(int i = chk-2; i >= 0; i--){
            if(ans[i] == 0){
                res.push_back(i);
                res.push_back(i);
            } else {
                // i부터, chk까지 res에 추가
                for(int j = i; j <= chk; j++)
                    res.push_back(j);

                // i부터 chk-1까지 청소
                for(int j = i; j <= chk-1; j++){
                    res.push_back(j);
                    res.push_back(j);
                }
            }
        }

        // chk+1을 0으로 가져오기
        for(int i = chk; i >= 0; i--)
            res.push_back(i);
    }

//    cout << "res size: " << res.size() << endl;
    cout << res.size() << endl;
    for (int idx : res) {
        cout << idx + 1 << " ";  // 1-based index로 출력
    }
    cout << endl;

    // 실제 시뮬레이션
    // res[i] = i : arr[i] = arr[i+1] = arr[i] ^ arr[i+1]


//    for(auto i : res){
//        ll x = arr[i] ^ arr[i + 1];
//        arr[i] = x;
//        arr[i + 1] = x;
//        cout << "arr : ";
//        for (auto v : arr) {
//            cout << v << ' ';
//        }
//        cout << endl;
//    }

//    cout << "arr[0]: " << k << ' ' << arr[0] << endl;
}

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

    int TC;
    cin >> TC;
    while (TC--) {
//        cout << "TC: " << TC << endl;
        solve();
    }
    return 0;
}

Submission Info

Submission Time
Task B - Adjacent Replace
User now_cow
Language C++ 23 (Clang 16.0.6)
Score 800
Code Size 7261 Byte
Status AC
Exec Time 8 ms
Memory 3636 KiB

Compile Error

./Main.cpp:12:8: warning: variable 'odd_xor' set but not used [-Wunused-but-set-variable]
    ll odd_xor = 0, even_xor = 0;
       ^
./Main.cpp:12:21: warning: variable 'even_xor' set but not used [-Wunused-but-set-variable]
    ll odd_xor = 0, even_xor = 0;
                    ^
2 warnings generated.

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 1
AC × 34
Set Name Test Cases
Sample 00_sample_00.txt
All 00_sample_00.txt, 01_test_00.txt, 01_test_01.txt, 01_test_02.txt, 01_test_03.txt, 01_test_04.txt, 01_test_05.txt, 01_test_06.txt, 01_test_07.txt, 01_test_08.txt, 01_test_09.txt, 01_test_10.txt, 01_test_11.txt, 01_test_12.txt, 01_test_13.txt, 01_test_14.txt, 01_test_15.txt, 01_test_16.txt, 01_test_17.txt, 01_test_18.txt, 01_test_19.txt, 01_test_20.txt, 01_test_21.txt, 01_test_22.txt, 01_test_23.txt, 01_test_24.txt, 01_test_25.txt, 01_test_26.txt, 01_test_27.txt, 01_test_28.txt, 01_test_29.txt, 01_test_30.txt, 01_test_31.txt, 01_test_32.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3480 KiB
01_test_00.txt AC 1 ms 3348 KiB
01_test_01.txt AC 1 ms 3452 KiB
01_test_02.txt AC 2 ms 3588 KiB
01_test_03.txt AC 2 ms 3580 KiB
01_test_04.txt AC 5 ms 3544 KiB
01_test_05.txt AC 4 ms 3536 KiB
01_test_06.txt AC 5 ms 3540 KiB
01_test_07.txt AC 5 ms 3468 KiB
01_test_08.txt AC 1 ms 3456 KiB
01_test_09.txt AC 3 ms 3488 KiB
01_test_10.txt AC 5 ms 3536 KiB
01_test_11.txt AC 5 ms 3440 KiB
01_test_12.txt AC 5 ms 3636 KiB
01_test_13.txt AC 1 ms 3516 KiB
01_test_14.txt AC 4 ms 3596 KiB
01_test_15.txt AC 4 ms 3612 KiB
01_test_16.txt AC 7 ms 3460 KiB
01_test_17.txt AC 8 ms 3480 KiB
01_test_18.txt AC 8 ms 3592 KiB
01_test_19.txt AC 8 ms 3544 KiB
01_test_20.txt AC 3 ms 3508 KiB
01_test_21.txt AC 2 ms 3572 KiB
01_test_22.txt AC 5 ms 3540 KiB
01_test_23.txt AC 5 ms 3552 KiB
01_test_24.txt AC 1 ms 3404 KiB
01_test_25.txt AC 1 ms 3348 KiB
01_test_26.txt AC 1 ms 3532 KiB
01_test_27.txt AC 1 ms 3484 KiB
01_test_28.txt AC 1 ms 3436 KiB
01_test_29.txt AC 1 ms 3524 KiB
01_test_30.txt AC 2 ms 3532 KiB
01_test_31.txt AC 2 ms 3568 KiB
01_test_32.txt AC 5 ms 3440 KiB