oj.uz

Submission #1091992

# Submission time Handle Problem Language Result Execution time Memory
1091992 2024-09-22T19:16:11 Z horiaboeriu XOR Sum (info1cup17_xorsum) C++17
100 / 100
 701 ms 19708 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2396 KB Output is correct
2 Correct 4 ms 2560 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 14708 KB Output is correct
2 Correct 338 ms 13968 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 14708 KB Output is correct
2 Correct 338 ms 13968 KB Output is correct
3 Correct 471 ms 18436 KB Output is correct
4 Correct 449 ms 16476 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2396 KB Output is correct
2 Correct 4 ms 2560 KB Output is correct
3 Correct 74 ms 3932 KB Output is correct
4 Correct 76 ms 3932 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2396 KB Output is correct
2 Correct 4 ms 2560 KB Output is correct
3 Correct 351 ms 14708 KB Output is correct
4 Correct 338 ms 13968 KB Output is correct
5 Correct 471 ms 18436 KB Output is correct
6 Correct 449 ms 16476 KB Output is correct
7 Correct 74 ms 3932 KB Output is correct
8 Correct 76 ms 3932 KB Output is correct
9 Correct 685 ms 19708 KB Output is correct
10 Correct 701 ms 19540 KB Output is correct
11 Correct 687 ms 19304 KB Output is correct