Submission #1140231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140231		Persia	XOR Sum (info1cup17_xorsum)	C++20	100 / 100	622 ms	17200 KiB

xorsum

#include <bits/stdc++.h>
#define bit(i, x) (x >> i & 1)
#define ll long long
const int N = 2e5 + 5;
const int mod = 998244353;
using namespace std;

int n;
vector<int> a, b, c;

int subtask1() {
    int res = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = i; j <= n; j++) {
            int x = a[i] + a[j];
            res = (res ^ x);
        }
    }
    return res;
}

int subtask2() {
    vector<int> cnt(4005);
    int res = 0;
    for(int i = 1; i <= n; i++) cnt[a[i]]++;
    for(int i = 1; i <= 4000; i++) {
        for(int j = i; j <= 4000; j++) {
            ll x = (i == j ? 1LL * cnt[i] * (cnt[i] + 1) / 2 : 1LL * cnt[i] * cnt[j]);
            x %= 2;
            if(x % 2) res ^= (i + j);
        }
    }
    return res;
}

ll subtask3() {
    vector<int> v(n, 0);

    auto calc = [&](ll x) -> ll { // Ham dem so cap <= x trong v, v phai sort san
        int sz = v.size();
        ll res = 0;

        for(int i = 0, j = sz - 1; i < sz; i++) {
            while(j >= i && v[i] + v[j] > x) j--;
            if(j >= i) res += j - i + 1;
        }

        return res;
    };

//    v.push_back(1);
//    v.push_back(3);
//    v.push_back(4);
//
//    cout << calc(4);

    ll res = 0;

    for(int i = 0; i < 30; i++) {
        // Xuat vector modulo 2^{i + 1} vao v
        // Sort lai v
        // Dung v va dem so cap <= x

        // Radix sort "a"
        b.clear();
        c.clear();
        for(int j = 1; j <= n; j++) {
            if(bit(i, a[j]) == 0) b.push_back(a[j]);
            else c.push_back(a[j]);
        }
        a.assign(1, 0);
        for(auto j : b) a.push_back(j);
        for(auto j : c) a.push_back(j);

        v.clear();
        for(int j = 1; j <= n; j++) v.push_back(a[j] % (1LL << (i + 1)));

        ll val = calc((1LL << (i + 1)) - 1) - calc((1LL << i) - 1);
        val += calc((1LL << (i + 2)) - 2) - calc((1LL << (i + 1)) + (1LL << i) - 1);
        if(val % 2) res |= (1LL << i);
    }

    return res;
}

bool check2() {
    return *max_element(a.begin() + 1, a.begin() + n + 1) <= 4000;
}

signed main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    a.assign(n + 3, 0);
    for(int i = 1; i <= n; i++) cin >> a[i];

    cout << subtask3();

//    if(check2()) cout << subtask2();
//    else cout << subtask1();

//    subtask3();

    return 0 ^ 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23