QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#608756 | #1899. Maximaze XOR sum | rgnerdplayer# | WA | 0ms | 3756kb | C++20 | 2.2kb | 2024-10-04 02:35:33 | 2024-10-04 02:35:33 |
Judging History
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