oj.uz

Submission #141569

# Submission time Handle Problem Language Result Execution time Memory
141569 2019-08-08T12:21:45 Z Ruxandra985 XOR Sum (info1cup17_xorsum) C++14
100 / 100
 790 ms 21416 KB 
 #include <cstdio>
#define INF 2000000000
using namespace std;
int v[1000010],w[1000010],w2[1000010];
int main()
{
    //FILE *fin = fopen ("a.in","r");
    //FILE *fout = fopen ("a.out","w");
    int n,bit,i,sol,b0=0,p1,p2,poz,nr;
    scanf ("%d",&n);
    for (i=1;i<=n;i++){
        scanf ("%d",&v[i]);
        w[i] = i;
        if (v[i]%2 == 0)
            b0++;
    }
    sol = 0;
    if ((long long)b0 * (n-b0)%2)
        sol++;
    w[n+1] = n+1;
    v[n+1] = INF;
    for (bit = 0 ; bit < 30 ; bit ++){
        b0 = 0;
        for (i=1;i<=n;i++){
            if ((v[i] & (1<<bit)) == 0)
                b0++;
        }
        p1 = 0;
        p2 = b0;
        for (i=1;i<=n;i++){
            if ((v[w[i]] & (1<<bit)) == 0)
                w2[++p1] = w[i];
            else
                w2[++p2] = w[i];
            /// vector auxiliar care are doar ultimii bit biti
        }
        /// facem cumva sa nu sortam w
        for (i=1;i<=n;i++)
            w[i] = w2[i]; /// indicii, dar valorile ar fi in ord cresc
        /// w e vector sortat doar cu ultimii bit biti
        /// ai numere intre 0 si 2^(bit+1) - 1
        poz = n+1;
        nr = 0;
        int x = 0;
        for (i=1;i<=n;i++){ /// prin w
            if (v[i] & (1<<(bit+1)))
                x++;
            if (poz <= i){ /// se cupleaza cu toate de dupa el
                poz = i;
                nr = nr + (n-i+1);
            }
            else {
                while (i<poz && (v[w[i]] & ((1<<(bit+1))-1)) + (v[w[poz-1]] & ((1<<(bit+1))-1)) >= (1<<(bit+1)))
                    poz--;
                nr = nr + (n - poz + 1);
            }
        }
        //printf ("%d %d\n",nr,x);
        nr = nr +  ( ((long long)x * (n - x))%2 );
        if (nr % 2)
            sol = sol + (1<<(bit+1));
    }
    printf ("%d",sol);
    return 0;
}

Compilation message

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

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 16632 KB Output is correct
2 Correct 465 ms 15480 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 16632 KB Output is correct
2 Correct 465 ms 15480 KB Output is correct
3 Correct 596 ms 18808 KB Output is correct
4 Correct 574 ms 18040 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 5 ms 376 KB Output is correct
3 Correct 74 ms 2468 KB Output is correct
4 Correct 75 ms 2424 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 5 ms 376 KB Output is correct
3 Correct 514 ms 16632 KB Output is correct
4 Correct 465 ms 15480 KB Output is correct
5 Correct 596 ms 18808 KB Output is correct
6 Correct 574 ms 18040 KB Output is correct
7 Correct 74 ms 2468 KB Output is correct
8 Correct 75 ms 2424 KB Output is correct
9 Correct 790 ms 21412 KB Output is correct
10 Correct 739 ms 21416 KB Output is correct
11 Correct 771 ms 21408 KB Output is correct