oj.uz

Submission #197390

# Submission time Handle Problem Language Result Execution time Memory
197390 2020-01-20T18:03:49 Z Pankin XOR Sum (info1cup17_xorsum) C++14
100 / 100
 1407 ms 15096 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define pii pair<int, int>

const int INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const int mod = 1000000007;
const int P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;

using namespace std;

const int N = 1000000 + 5;
int order[N], p0[N], p1[N], o0, o1, a[N], n, ans = 0;

inline int readint() {
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x;
}

signed main() {
    fast_io;

    n = readint();
    int mx = 0;
    for (int i = 0; i < n; i++) {
        a[i] = readint();
        mx = max(mx, a[i]);
        order[i] = i;
    }

    if (mx <= 1000000)
        mx = 21;
    else
        mx = 30;

    int curmask = 0;
    int pointer0 = o0, pointer1 = o1, same = 0, col = 0;
    for (int bit = 0; bit < mx; bit++) {
        o0 = o1 = 0;

        for (int i = 0; i < n; i++) {
            int v = (a[order[i]]>>bit)&1;
            if (v) {
                p1[o1] = order[i];
                o1++;
            }
            else {
                p0[o0] = order[i];
                o0++;
            }
        }

        pointer0 = o0, pointer1 = o1, same = 0, col = 0;
        for (int i = 0; i < n; i++) {

            while(pointer0 > 0 && (a[p0[pointer0 - 1]]&curmask) + (a[order[i]]&curmask) >= (1 << bit))
                pointer0--;
            if (((a[order[i]]>>bit)&1) != 0)
                col += pointer0;
            else
                col += o0 - pointer0;

            while(pointer1 > 0 && (a[p1[pointer1 - 1]]&curmask) + (a[order[i]]&curmask) >= (1 << bit))
                pointer1--;
            if (((a[order[i]]>>bit)&1) != 1)
                col += pointer1;
            else
                col += o1 - pointer1;

            if (((a[order[i]] + a[order[i]])>>bit)&1)
                same++;
            col &= 3;
        }
        col += 4 - (same&3);
        col >>= 1;
        col += same;

        ans |= ((col&1) << bit);

        int cur = 0;
        for (int i = 0; i < o0; i++) {
            order[cur] = p0[i];
            cur++;
        }
        for (int i = 0; i < o1; i++) {
            order[cur] = p1[i];
            cur++;
        }

        curmask <<= 1;
        curmask++;
    }

    cout << ans;

    return 0;
}

/*
2
7 0
*/

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 499 ms 15068 KB Output is correct
2 Correct 461 ms 13988 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 15068 KB Output is correct
2 Correct 461 ms 13988 KB Output is correct
3 Correct 736 ms 14968 KB Output is correct
4 Correct 712 ms 14668 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 120 ms 1892 KB Output is correct
4 Correct 118 ms 1772 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 499 ms 15068 KB Output is correct
4 Correct 461 ms 13988 KB Output is correct
5 Correct 736 ms 14968 KB Output is correct
6 Correct 712 ms 14668 KB Output is correct
7 Correct 120 ms 1892 KB Output is correct
8 Correct 118 ms 1772 KB Output is correct
9 Correct 1250 ms 15096 KB Output is correct
10 Correct 1221 ms 15096 KB Output is correct
11 Correct 1407 ms 15020 KB Output is correct