Submission #1302198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302198		daotuankhoi	XOR Sum (info1cup17_xorsum)	C++20	56 / 100	1696 ms	16092 KiB

xorsum

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template <class T> bool ckmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template <class T> bool ckmin(T &a, T b) { return a > b ? (a = b, true) : false; }

const int MAXN = 1e6 + 5;
ll n, a[MAXN], b[MAXN], tmp[MAXN];

void radix(int 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 ((b[i] >> bit) & 1) tmp[p1++] = a[i];
        else tmp[p0++] = a[i];
    }

    for (int i = 1; i <= n; i++) a[i] = tmp[i];
}

ll calc(int bit) {
    for (int i = 1; i <= n; i++) {
        b[i] = a[i] & ((1LL << (bit + 1)) - 1);
    }
    sort(b + 1, b + n + 1);
    int l1 = n, r1 = n, l2 = n, r2 = n;

    ll lo1 = 1LL << bit, lo2 = lo1 + (1LL << (bit + 1));
    ll hi1 = (1LL << (bit + 1)), hi2 = (1LL << (bit + 2));
    ll 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;
}

int main() {
    #define NAME "test"
    if (fopen(NAME".inp", "r")) {
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    ll ans = 0;
    for (int i = 0; i <= 30; i++) {
        if (calc(i) & 1) ans |= (1 << i);
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

xorsum.cpp: In function 'int main()':
xorsum.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
xorsum.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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