QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#60110 | #1899. Maximaze XOR sum | abdelrahman001# | WA | 2ms | 3716kb | C++20 | 1.4kb | 2022-11-02 21:22:24 | 2022-11-02 21:22:25 |
Judging History
answer
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int N = 1e5 + 5;
int n;
ll a[N], b[N], xr, xr2;
struct gauss {
vector<pair<ll, int>> setOfXors;
void ins(ll x, int i) { ///Add X to Gaussian Basis
for (auto v : setOfXors)
x = min(x, x ^ v.first);
if(x)
setOfXors.push_back({x, i});
}
pair<ll, vector<int>> qry(ll x, ll xr2) { ///Get maximum subsequence XOR ^ x
vector<int> ret;
for (auto v : setOfXors) {
ll nxt = x ^ v.first;
if(nxt + (nxt ^ xr2) > x + (xr2 ^ x)) {
x ^= v.first;
ret.push_back(v.second);
}
}
return {x, ret};
}
};
int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
gauss G;
cin >> n;
for(int i = 1;i <= n;i++) {
cin >> a[i];
xr ^= a[i];
xr2 ^= a[i];
}
for(int i = 1;i <= n;i++) {
cin >> b[i];
xr2 ^= b[i];
G.ins(a[i] ^ b[i], i);
}
auto ret = G.qry(xr, xr2);
cout << ret.first + (xr2 ^ ret.first) << " " << ret.second.size() << '\n';
for(auto i : ret.second)
cout << i << " ";
cout << endl;
return 0;
}
// xr = xor of all a
// xr2 = xor of all a and b
// c_i = a_i ^ b_i
// query of(xr) = maximum xor for a with the needed swaps
// ans = query of(xr) + (xr2 ^ query of(xr))
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3540kb
input:
2 1 1 2 2
output:
6 1 1
result:
ok n=2
Test #2:
score: 0
Accepted
time: 2ms
memory: 3624kb
input:
3 2 1 4 4 0 4
output:
7 0
result:
ok n=3
Test #3:
score: 0
Accepted
time: 2ms
memory: 3636kb
input:
10 12 0 4 3 1 1 12 3 11 11 3 3 14 6 14 15 1 15 5 2
output:
26 1 1
result:
ok n=10
Test #4:
score: 0
Accepted
time: 2ms
memory: 3716kb
input:
50 9 27 19 1 31 10 2 7 25 26 12 25 15 18 11 15 30 25 31 2 5 30 8 18 8 17 14 2 17 7 26 26 10 25 26 5 3 5 1 17 18 12 4 17 14 19 30 30 20 2 13 18 3 8 18 11 31 20 21 14 17 29 31 2 5 28 31 17 10 13 6 10 22 18 10 2 0 15 7 14 4 15 25 10 3 30 3 21 0 12 11 19 4 16 27 10 26 3 2 5
output:
35 0
result:
ok n=50
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 3628kb
input:
100 50 13 42 41 8 21 50 18 21 50 9 27 51 10 43 26 29 6 52 44 52 19 39 47 59 35 42 6 27 41 8 25 32 32 45 18 57 5 46 32 60 24 63 56 31 32 58 15 0 36 31 33 31 50 14 45 31 27 15 55 8 53 10 5 8 24 15 35 45 34 16 31 44 51 34 13 30 49 0 4 62 6 8 30 44 29 59 60 45 40 1 0 40 29 35 18 42 52 15 28 35 43 24 14 ...
output:
77 2 2 6
result:
wrong answer Wrong sum