Submission #3776961


Source Code Expand

#include <vector>

using namespace std;

using u8 = unsigned char;
using uint = unsigned int;

class bitVector {
public:
    uint length, cnum, bnum;
    static int cw, bw;
    vector<uint> bit;
    vector<uint> chunk;
    vector<vector<u8>> blocks;


    explicit bitVector(int N) : length(N) {
        cnum = (length + cw - 1) / cw;
        bnum = cw / bw;

        bit.assign(cnum * bnum, 0);
        chunk.assign(cnum + 1, 0);
        blocks.assign(cnum, vector<u8>(bnum, 0));
    }

    void set(int pos, int b) {
        int bpos = pos / bw;
        int offset = pos % bw;

        if (b == 0) {
            bit[bpos] &= ~(1 << offset);
        } else if (b == 1) {
            bit[bpos] |= (1 << offset);
        }
    }

    int access(int pos) const {
        int bpos = pos / bw;
        int offset = pos % bw;
        return bit[bpos] >> offset & 1;
    }

    uint popCount(uint num) const {
        return __builtin_popcount(num);
    }

    void build() {
        chunk[0] = 0;
        for (int i = 0; i < cnum; ++i) {
            blocks[i][0] = 0;
            for (int j = 0; j < bnum - 1; ++j) {
                blocks[i][j + 1] = blocks[i][j] + popCount(bit[i * bnum + j]);
            }
            chunk[i + 1] = chunk[i] + blocks[i][bnum - 1] + popCount(bit[(i + 1) * bnum - 1]);
        }
    }

    int rank(int pos, int kind) const {
        if (kind == 0) {
            return pos - rank1(pos);
        } else {
            return rank1(pos);
        }
    }

    int rank1(int pos) const {
        int cpos = pos / cw;
        int bpos = pos % cw / bw;
        int offset = pos % bw;

        uint masked = (bit[cpos * bnum + bpos]) & ((1 << offset) - 1);
        return chunk[cpos] + blocks[cpos][bpos] + popCount(masked);
    }

    int select(int num, int kind) const {
        if (num == 0) return 0;
        if (rank(length, kind) < num) return -1;

        int ok = length, ng = 0;
        while (ok - ng > 1) {
            int mid = (ok + ng) / 2;
            if (rank(mid, kind) >= num) {
                ok = mid;
            } else {
                ng = mid;
            }
        }

        return ok;
    }
};

int bitVector::cw = 256;
int bitVector::bw = 32;

class WaveletMatrix {
public:
    int length, data_size;
    vector<bitVector> bvs;
    vector<int> znum;

    explicit WaveletMatrix(vector<long long> data, int _data_size) : length(data.size()), data_size(_data_size) {
        bvs.assign(data_size, bitVector(length));
        znum.assign(data_size, 0);

        vector<long long> tmp[2];
        for (int k = data_size - 1; k >= 0; --k) {
            for (int i = 0; i < length; ++i) {
                int b = (data[i] >> k) & 1;
                bvs[k].set(i, b);
                tmp[b].push_back(data[i]);
            }
            bvs[k].build();

            znum[k] = tmp[0].size();

            data.clear();
            for (int b = 0; b < 2; ++b) {
                copy(tmp[b].begin(), tmp[b].end(), back_inserter(data));
                tmp[b].clear();
            }
        }
    }

    // 0-indexed
    // 元のデータのdata[pos]を返す
    long long access(int pos) {
        long long ret = 0;

        for (int k = data_size - 1; k >= 0; --k) {
            long long b = bvs[k].access(pos);
            ret += b << k;
            pos = bvs[k].rank(pos + 1, b) - 1;
            if (b == 1) pos += znum[k];
        }

        return ret;
    }

    // [0, pos)にあるkindの数
    int rank(int pos, long long kind) {
        int from = 0, to = pos;

        for (int k = data_size - 1; k >= 0; --k) {
            int b = (kind >> k) & 1;
            from = bvs[k].rank(from, b);
            to = bvs[k].rank(to, b);
            if (b == 1) {
                from += znum[k];
                to += znum[k];
            }
        }

        return to - from;
    }

    // [0, pos)にあるkind未満の数
    int rank_less(int pos, long long kind) {
        int from = 0, to = pos;
        int ret = 0;

        for (int k = data_size - 1; k >= 0; --k) {
            int b = (kind >> k) & 1;
            if (b == 1) {
                ret += bvs[k].rank(to, 0) - bvs[k].rank(from, 0);
            }

            from = bvs[k].rank(from, b);
            to = bvs[k].rank(to, b);

            if (b == 1) {
                from += znum[k];
                to += znum[k];
            }
        }

        return ret;
    }

    // [0, pos)にkindがnum個あるような最小のpos
    // そもそもnum個なければ-1
    int select(long long kind, int num) {
        if (num == 0) return 0;
        if (rank(length, kind) < num) return -1;

        int ok = length, ng = 0;
        while (ok - ng > 1) {
            int mid = (ok + ng) / 2;
            if (rank(mid, kind) >= num) {
                ok = mid;
            } else {
                ng = mid;
            }
        }

        return ok;
    }
};

#include <iostream>

int main() {
    int N;
    cin >> N;

    vector<long long> a(N), b(N);
    vector<long long> a_bit(30, 0), b_bit(30, 0);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
        for (int k = 0; k < 30; ++k) {
            a_bit[k] += (a[i] << k) & 1;
        }
    }
    for (int i = 0; i < N; ++i) {
        cin >> b[i];
        for (int k = 0; k < 30; ++k) {
            b_bit[k] += (b[i] << k) & 1;
        }
    }

    int ans = 0;
    for (int k = 0; k < 30; ++k) {
        ans ^= (a_bit[k] * (N - b_bit[k]) + b_bit[k] * (N - a_bit[k])) & 1;
    }

    for (int k = 0; k < 29; ++k) {
        int mask = (1LL << k) - 1;

        vector<long long> c(N);
        for (int i = 0; i < N; ++i) {
            c[i] = b[i] & mask;
        }

        WaveletMatrix wm(c, k + 2);
        for (int i = 0; i < N; ++i) {
            int dec = a[i] & mask;
            int cnt = N - wm.rank_less(N, (1LL << k) - dec);
            ans ^= (cnt & 1) << k;
        }
    }

    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task D - Two Sequences
User Tiramister
Language C++14 (GCC 5.4.1)
Score 0
Code Size 6157 Byte
Status WA
Exec Time 3156 ms
Memory 12264 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 4
AC × 7
WA × 3
TLE × 6
Set Name Test Cases
Sample example_0, example_1, example_2, example_3
All N100000_0, N100000_1, N150000_0, N150000_1, N200000_0, N200000_1, N200000_ex_0, N200000_ex_1, example_0, example_1, example_2, example_3, rand_0, rand_1, smallrand_0, smallrand_1
Case Name Status Exec Time Memory
N100000_0 WA 2459 ms 6300 KB
N100000_1 AC 2451 ms 6268 KB
N150000_0 TLE 3156 ms 10068 KB
N150000_1 TLE 3156 ms 9604 KB
N200000_0 TLE 3156 ms 12032 KB
N200000_1 TLE 3156 ms 11832 KB
N200000_ex_0 TLE 3156 ms 12264 KB
N200000_ex_1 TLE 3156 ms 11796 KB
example_0 AC 2 ms 256 KB
example_1 AC 2 ms 256 KB
example_2 AC 2 ms 256 KB
example_3 AC 2 ms 256 KB
rand_0 AC 149 ms 712 KB
rand_1 WA 324 ms 1100 KB
smallrand_0 AC 2 ms 256 KB
smallrand_1 WA 2 ms 256 KB