Submission #45374

#	Time	Username	Problem	Language	Result	Execution time	Memory
45374		model_code	XOR Sum (info1cup17_xorsum)	C++17	100 / 100	847 ms	8564 KiB

xorsum

#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 (stderr)

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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 38 / 38
• Subtask 5: 23 / 23