Submission #1310189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310189		nguyenkhangninh99	XOR Sum (info1cup17_xorsum)	C++20	100 / 100	620 ms	23916 KiB

xorsum

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

#define int long long
const int maxn = 1e6 + 5;
int a[maxn], b[maxn], tmp[maxn], n;
int calc(int bit){
    for(int i = 1; i <= n; i++) b[i] = a[i] & ((1LL << (bit + 1)) - 1);
    int l1 = n, r1 = n, l2 = n, r2 = n;

    int lo1 = 1LL << bit, lo2 = lo1 + (1LL << (bit + 1));
    int hi1 = (1LL << (bit + 1)), hi2 = (1LL << (bit + 2));
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        while (l1 > 0 && lo1 - b[i] <= b[l1]) l1--;
        while (l2 > 0 && lo2 - b[i] <= b[l2]) l2--;
        while (r1 > 0 && hi1 - b[i] <= b[r1]) r1--;
        while (r2 > 0 && hi2 - b[i] <= b[r2]) r2--;
        ans += r1 - l1 + r2 - l2 + (lo1 <= b[i] * 2 && b[i] * 2 < hi1) + (lo2 <= b[i] * 2 && b[i] * 2 < hi2);

    }
    return ans / 2;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

   // freopen("SUMXOR.inp", "r", stdin);
   // freopen("SUMXOR.inp", "r", stdin);

    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int ans = 0;
    for(int bit = 0; bit <= 30; bit++){
        int cnt0 = 0;
        for(int i = 1; i <= n; i++) if (((a[i] >> bit) & 1) == 0) cnt0++;

        int p0 = 1, p1 = cnt0 + 1;
        for(int i = 1; i <= n; i++){
            if((a[i] >> bit) & 1) tmp[p1++] = a[i];
            else tmp[p0++] = a[i];
        }

        for(int i = 1; i <= n; i++) a[i] = tmp[i];
        ans |= ((calc(bit) & 1) << bit);
    }
    cout << ans;
}

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