제출 #1091992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1091992		horiaboeriu	XOR Sum (info1cup17_xorsum)	C++17	100 / 100	701 ms	19708 KiB

xorsum

#include <bits/stdc++.h>

using namespace std;
#define MAXN 1000000
#define MAXB 29
int v[MAXN], v1[MAXN], v2[MAXN];
long long rez[MAXB + 1];
int readInt() {
    int x;
    char ch;
    ch = fgetc(stdin);
    while (isspace(ch)) {
        ch = fgetc(stdin);
    }
    x = 0;
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = fgetc(stdin);
    }
    return x;
}
int main()
{
    int n, i, b, p, nr1, nr2, nr, j, k, i1, i2, poz;
    n = readInt();
    for (i = 0; i < n; i++) {
        v[i] = readInt();
    }
    sort(v, v + n);
    nr = 0;
    for (b = 29; b >= 0; b--) {
        //trebuie sa le tin sortate dupa ce fac % (1 << b) deci intercalsez resturile de la b + 1
        //ca o sa fie 2 secv crescatoare
        p = (1 << (b + 1));
        poz = 0;
        while (poz < n && v[poz] < p) {
            poz++;
        }
        for (i = 0; i < n; i++) {
            v[i] %= p;// &= (p - 1)
        }
        //interclasez
        nr1 = 0;
        while (nr1 < poz) {
            v1[nr1] = v[nr1];
            nr1++;
        }
        for (nr2 = 0; nr2 < n - nr1; nr2++) {
            v2[nr2] = v[nr1 + nr2];
        }
        n = i1 = i2 = 0;
        while (i1 < nr1 && i2 < nr2) {
            if (v1[i1] < v2[i2]) {
                v[n] = v1[i1];
                i1++;
            } else {
                v[n] = v2[i2];
                i2++;
            }
            n++;
        }
        while (i1 < nr1) {
            v[n] = v1[i1];
            i1++;
            n++;
        }
        while (i2 < nr2) {
            v[n] = v2[i2];
            i2++;
            n++;
        }
        //trebuie sa vad daca va aparea bitul b in rezultat
        //adica numarul de sume care au bitul b sa fie impar ca sa apara
        //si pentru un numar x, apare bitul b daca il adun cu orice numar y,din intervalul p / 2 - x, p - 1 - x
        for (i = 0; i < n; i++) {
            if ((2 * v[i]) % p >= p / 2) {//ca sa pot imparti la 2 la final ca am adunat toate sumele de 2 ori
                rez[b]++;
            }
        }
        j = k = n - 1;
        i = 0;
        while (i < n && v[i] <= p / 2) {
            while (k >= 0 && v[k] > p - 1 - v[i]) {
                k--;
            }
            //k este cel mai mare care da o suma corecta
            if (j > k) {
                j = k;
            }
            while (j >= 0 && (v[i] + v[j]) % p >= p / 2) {
                j--;
            }
            //acum j este ultimul care nu mai da o suma corecta si v[j] < v[k]
            rez[b] += k - j;
            i++;
        }
        //acum sunt doua intervale pentru care va fi suma buna
        //unul de la k la 0 si altul de la n - 1 la j + 1
        j = n - 1;
        for (; i < n; i++) {
            while (k >= 0 && (v[i] + v[k]) % p < p / 2) {
                k--;
            }
            while (j >= 0 && (v[i] + v[j]) % p >= p / 2) {
                j--;
            }
            rez[b] += k + 1 + n - 1 - j;
        }
        rez[b] /= 2;
        rez[b] %= 2;

        if (rez[b] > 0) {
            nr += p / 2;
        }
    }
    printf("%d\n", nr);
    return 0;
}

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