QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#60107 | #1899. Maximaze XOR sum | abdelrahman001# | WA | 2ms | 3568kb | C++20 | 1.3kb | 2022-11-02 21:13:19 | 2022-11-02 21:13:21 |
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) { ///Get maximum subsequence XOR ^ x
vector<int> ret;
for (auto v : setOfXors) {
if(x ^ v.first > 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);
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))
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3528kb
input:
2 1 1 2 2
output:
6 1 1
result:
ok n=2
Test #2:
score: 0
Accepted
time: 2ms
memory: 3568kb
input:
3 2 1 4 4 0 4
output:
7 2 1 2
result:
ok n=3
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 3568kb
input:
10 12 0 4 3 1 1 12 3 11 11 3 3 14 6 14 15 1 15 5 2
output:
20 4 1 2 3 6
result:
wrong answer Jury has better answer