제출 #141569

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
141569		Ruxandra985	XOR Sum (info1cup17_xorsum)	C++14	100 / 100	790 ms	21416 KiB

xorsum

 #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;
}

컴파일 시 표준 에러 (stderr) 메시지

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