Submission #389337

#	Time	Username	Problem	Language	Result	Execution time	Memory
389337		cheissmart	XOR Sum (info1cup17_xorsum)	C++14	0 / 100	665 ms	4236 KiB

xorsum

#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << "): " << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

int cnt[2][2][33];

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    int n;
    cin >> n;
    vi a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    for(int bit = 0; bit < 30; bit++) {
        memset(cnt, 0, sizeof cnt);
        for(int i = 0; i < n; i++) {
            int c = a[i] >> bit & 1;
            int same = 0, nxt = 0;
            if(bit) nxt = a[i] >> (bit - 1) & 1;
            for(int j = bit - 1; j >= 0; j--) {
                if((a[i] >> j & 1) ^ nxt) break;
                same++;
            }
            cnt[c][nxt][same]++;
        }
        ll odd_cnt = 0;
        for(int i1 = 0; i1 < 2; i1++) {
            for(int j1 = 0; j1 < 2; j1++) {
                for(int k1 = 0; k1 < 32; k1++) {
                    for(int i2 = 0; i2 < 2; i2++) {
                        for(int j2 = 0; j2 < 2; j2++) {
                            for(int k2 = 0; k2 < 32; k2++) {
                                int c1 = cnt[i1][j1][k1];
                                int c2 = cnt[i2][j2][k2];
                                int res = i1 ^ i2;
                                if(j1 && j2) res ^= 1;
                                else if(j1) {
                                    if(k2 < k1) res ^= 1;
                                } else if(j2) {
                                    if(k1 < k2) res ^= 1;
                                }
                                if(res) odd_cnt += (ll) c1 * c2;
                            }
                        }
                    }
                }
            }
        }
        for(int i = 0; i < n; i++) if((2 * a[i]) >> bit & 1)
            odd_cnt++;
        assert(odd_cnt % 2 == 0);
        odd_cnt /= 2;
        if(odd_cnt & 1) ans |= 1 << bit;
    }
    cout << ans << '\n';

}

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