Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
- template<typename T = int, int BITS = 30>
- struct xor_basis {
- T basis[BITS];
- int r = 0;
- xor_basis() {
- for(int i = 0; i < BITS; i++) {
- basis[i] = 0;
- }
- }
- bool insert(T x, int id = -1) {
- if(contains(x)) return false;
- for(int b = BITS - 1; b >= 0; b--) {
- if(x >> b & 1) {
- if(basis[b]) {
- x ^= basis[b];
- } else {
- basis[b] = x;
- r++;
- return true;
- }
- }
- }
- return false;
- }
- bool contains(T x) const {
- return min_value(x) == 0;
- }
- T min_value(T x) const {
- if(r == BITS) return 0;
- for(int i = BITS - 1; i >= 0; i--) x = min(x, x ^ basis[i]);
- return x;
- }
- int reduce(T pref, int from_bit) const {
- for(int b = BITS - 1; b >= from_bit; b--) {
- if(pref >> b & 1 && basis[b]) {
- pref ^= basis[b];
- }
- }
- return pref;
- }
- int can_make_prefix(T ai, T pref, int from_bit) const {
- T now = ai ^ pref;
- T v = reduce(now, from_bit);
- return (v >> from_bit) == 0;
- }
- T max_value(T ai, T bi) const { // find maximum x <= bi such that ai ^ x exists
- T x = 0;
- T mx = ai <= bi ? ai : -1;
- for(int i = BITS - 1; i >= 0; i--) {
- int b_bit = bi >> i & 1;
- if(can_make_prefix(ai, x, i)) {
- T pref = reduce(x ^ ai, i);
- T nx = x;
- for(int j = i - 1; j >= 0; j--) {
- int change = 0;
- if((nx | (1ll << j)) <= bi) {
- change = 1;
- nx |= 1ll << j;
- pref ^= 1ll << j;
- }
- if(pref >> j & 1) {
- if(basis[j]) {
- pref ^= basis[j];
- } else {
- pref ^= 1ll << j;
- nx ^= change << j;
- }
- }
- }
- if(can_make_prefix(ai, nx, 0)) {
- mx = max(mx, nx);
- }
- }
- if(b_bit) {
- x |= 1ll << i;
- if(!can_make_prefix(ai, x, i)) break;
- }
- }
- return mx;
- }
- };
- void solve() {
- int n; cin >> n;
- vector<int> a(n);
- for(auto& x : a) {
- cin >> x;
- }
- xor_basis<int> xr;
- xr.insert(a[n - 1]);
- for(int i = n - 2; i >= 0; i--) {
- int mx = xr.max_value(a[i], a[i + 1]);
- if(mx == -1) {
- cout << -1 << '\n';
- return;
- }
- a[i] = mx;
- xr.insert(a[i]);
- }
- for(int i = 0; i < n; i++) {
- cout << a[i] << (i == n - 1 ? '\n' : ' ');
- }
- }
- signed main() {
- IOS;
- int t = 1;
- cin >> t;
- for(int i = 1; i <= t; i++) {
- //cout << "Case #" << i << ": ";
- solve();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment