oj.uz

Submission #373501

# Submission time Handle Problem Language Result Execution time Memory
373501 2021-03-04T22:22:08 Z qpwoeirut XOR Sum (info1cup17_xorsum) C++17
32 / 100
 497 ms 19180 KB 
//xorsum.cpp created at 03/04/21 10:30:22

#include <bits/stdc++.h>

using namespace std;

const int MN = 1000006;
const int LG = 21;

int N;
int A[MN];
int psum[(1 << LG) + 1];

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> N;
    for (int i=0; i<N; ++i) {
        cin >> A[i];
        assert(A[i] < (1 << (LG - 1)));
    }

    int ans = 0;
    for (int i=0; i<LG; ++i) {
        fill(psum, psum + (1 << LG) + 1, 0);
        for (int j=0; j<N; ++j) {
            const int val = A[j] & ((1 << (i + 1)) - 1);
            ++psum[val + 1]; // add 1 for easy indexing stuff
        }
        for (int j=1; j<=(1 << LG); ++j) {
            psum[j] += psum[j - 1];
        }
        //cerr << "psum:"; for (int j=1; j<=10; ++j) { cerr << ' ' << psum[j]; } cerr << endl;

        // range [2^i, 2^(i+1)) and [2^(i+1) + 2^i, 2^(i+2))
        int ct = 0;
        for (int j=0; j<N; ++j) {
            //cerr << "start: " << i << ' ' << j << ' ' << ct << endl;
            const int val = A[j] & ((1 << (i + 1)) - 1);
            const int lo1 = max(0, (1 << i) - val);
            const int hi1 = (1 << (i + 1)) - val;
            ct += psum[hi1] - psum[lo1];
            //cerr << "range1: " << i << ' ' << j << ' ' << ct << endl;

            const int lo2 = min(1 << LG, (1 << (i + 1)) + (1 << i) - val);
            const int hi2 = min(1 << LG, (1 << (i + 2)) - val);
            ct += psum[hi2] - psum[lo2];
            //cerr << "range2: " << i << ' ' << j << ' ' << ct << endl;

            ct += ((A[j] << 1) >> i) & 1;
            //cerr << "dupe: " << i << ' ' << j << ' ' << ct << endl;
        }
        //cerr << i << ' ' << ct << endl;

        assert((ct & 1) == 0);
        ct = (ct >> 1) & 1;
        ans += ct << i;
    }

    cout << ans << '\n';
}

/*
4  
3 9 6 6 

00110   1 1
01100   1 2
01001   1 3
01001   1 4
10010   2 2
01111   2 3
01111   2 4
01100   3 3
01100   3 4
01100   4 4
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 620 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 12612 KB Output is correct
2 Correct 380 ms 16512 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 12612 KB Output is correct
2 Correct 380 ms 16512 KB Output is correct
3 Correct 497 ms 19180 KB Output is correct
4 Correct 491 ms 19052 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 620 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 620 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -