Submission #74714890

---

Source Code Expand

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
ll xor_upto(ll n) {
    if (n < 0) return 0;
    if (n % 4 == 0) return n;
    if (n % 4 == 1) return 1;
    if (n % 4 == 2) return n + 1;
    return 0;
}
ll get_range_xor(ll L, ll R, ll C) {
    if (C == 0) return 0;
    ll res = 0;
    
    for (ll i = L; i <= R; ++i) {
        res ^= (i * C);
    }
    return res;
}

void solve() {
    int N;
    ll M;
    if (!(cin >> N >> M)) return;
    vector<ll> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    ll total_xor = 0;
    ll k = 1;

    while (k <= M) {
        ll current_f = 0;
        ll current_rem = k;
        ll slack = M - k + 1; 

        for (int i = 0; i < N; ++i) {
            if (current_rem >= A[i]) {
                current_rem -= A[i];
                current_f += A[i];
            } else {
                slack = min(slack, A[i] - current_rem - 1);
            }
        }

        ll L = k;
        ll R = k + slack;
        R = min(R, M);
        total_xor ^= get_range_xor(L, R, current_f);

        k = R + 1;
    }
    cout << total_xor << "\n";
}

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

    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

Submission Info

Judge Result