oj.uz

Submission #45374

# Submission time Handle Problem Language Result Execution time Memory
45374 2018-04-13T03:41:34 Z model_code XOR Sum (info1cup17_xorsum) C++17
100 / 100
 847 ms 8564 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1000009;

int x[nmax] , aux[nmax];
int i , b , p1 , p2 , p3 , cnt0 , answer , n;

void makeModulo()
{
    int u , act , i , j;

    for (i = 1 ; i <= n ; ++i)
    aux[i] = x[i];

    for (u = 1 ; u <= n ; ++u)
    if (aux[u] >= (1 << (b + 1))) break;

    for (i = u ; i <= n ; ++i)
    aux[i] %= (1 << (b + 1));

    i = 1 , j = u , act = 0;
    while (i <= u - 1 && j <= n)
    {
        if (aux[i] <= aux[j]) x[++act] = aux[i++];
        else x[++act] = aux[j++];
    }

    while (i <= u - 1) x[++act] = aux[i++];
    while (j <= n) x[++act] = aux[j++];
}

int main()
{
//freopen("xorsum.in" , "r" , stdin);
//freopen("xorsum.out" , "w" , stdout);

scanf("%d" , &n);

for (i = 1 ; i <= n ; ++i)
scanf("%d" , &x[i]);

sort(x + 1 , x + n + 1);

for (b = 29 ; 0 <= b ; --b) // % 2 ^ (b + 1)
{
    makeModulo();

    p1 = p2 = p3 = n + 1;
    for (i = 1 ; i <= n ; ++i)
    {
        if (p1 < i) p1 = i;
        if (p2 < i) p2 = i;
        if (p3 < i) p3 = i;

        while (i + 1 <= p1 && 1 * (1 << b) - x[i] <= x[p1 - 1]) p1--;
        while (i + 1 <= p2 && 2 * (1 << b) - x[i] <= x[p2 - 1]) p2--;
        while (i + 1 <= p3 && 3 * (1 << b) - x[i] <= x[p3 - 1]) p3--;

        cnt0 = p2 - p1 + n + 1 - p3;
        if (cnt0 % 2) answer ^= (1 << b);
    }
}

printf("%d\n" , answer);

return 0;
}

Compilation message

xorsum.cpp: In function 'int main()':
xorsum.cpp:39:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d" , &n);
 ~~~~~^~~~~~~~~~~
xorsum.cpp:42:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d" , &x[i]);
 ~~~~~^~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 8268 KB Output is correct
2 Correct 450 ms 8268 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 518 ms 8268 KB Output is correct
2 Correct 450 ms 8268 KB Output is correct
3 Correct 622 ms 8324 KB Output is correct
4 Correct 604 ms 8324 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 81 ms 8324 KB Output is correct
4 Correct 86 ms 8324 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 518 ms 8268 KB Output is correct
4 Correct 450 ms 8268 KB Output is correct
5 Correct 622 ms 8324 KB Output is correct
6 Correct 604 ms 8324 KB Output is correct
7 Correct 81 ms 8324 KB Output is correct
8 Correct 86 ms 8324 KB Output is correct
9 Correct 847 ms 8564 KB Output is correct
10 Correct 795 ms 8564 KB Output is correct
11 Correct 847 ms 8564 KB Output is correct