QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#608756#1899. Maximaze XOR sumrgnerdplayer#WA 0ms3756kbC++202.2kb2024-10-04 02:35:332024-10-04 02:35:33

Judging History

你现在查看的是最新测评结果

  • [2024-10-04 02:35:33]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3756kb
  • [2024-10-04 02:35:33]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

vector<int> operator+(vector<int> a, vector<int> b) {
    vector<int> c;
    set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(c));
    return c;
}

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

    auto solve = [&]() {
        int n;
        cin >> n;

        vector<i64> a(n), b(n);
        i64 A = 0, B = 0;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            A ^= a[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> b[i];
            B ^= b[i];
        }

        constexpr int L = 60;
        vector<i64> basis(L);
        vector<vector<int>> at(L);

        for (int i = 0; i < n; i++) {
            i64 x = a[i] ^ b[i];
            for (int j = L - 1; j >= 0; j--) {
                if (x >> j & 1) {
                    if (basis[j] == 0) {
                        basis[j] = x;
                        at[j] = {i};
                    }
                    x ^= basis[j];
                    at[j] = at[j] + vector{i};
                }
            }
        }

        vector<int> swaps;

        for (int bit = L - 1; bit >= 0; bit--) {
            if (A >> bit & 1 && B >> bit & 1) {
                continue;
            } else if (A >> bit & 1 || B >> bit & 1) {
                i64 x = basis[bit] & ~(1LL << bit);
                auto v = at[bit];
                for (int j = bit - 1; j >= 0; j--) {
                    if (x >> j & 1) {
                        if (basis[j] == 0) {
                            basis[j] = x;
                            at[j] = v;
                        }
                        x ^= basis[j];
                        v = v + at[j];
                    }
                }
            } else {
                if (basis[bit] != 0) {
                    A ^= basis[bit], B ^= basis[bit];
                    swaps = swaps + at[bit];
                }
            }
        }

        cout << A + B << ' ' << swaps.size() << '\n';
        for (auto i : swaps) {
            cout << i + 1 << " \n"[i == swaps.back()];
        }
    };
    
    solve();
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3532kb

input:

2
1 1
2 2

output:

6 1
2

result:

ok n=2

Test #2:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

3
2 1 4
4 0 4

output:

7 0

result:

ok n=3

Test #3:

score: -100
Wrong Answer
time: 0ms
memory: 3756kb

input:

10
12 0 4 3 1 1 12 3 11 11
3 3 14 6 14 15 1 15 5 2

output:

26 7
3 5 6 7 8 9 10

result:

wrong answer Wrong sum