Guest User

Untitled

a guest
Oct 29th, 2025
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.23 KB | Source Code | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  4.  
  5. template<typename T = int, int BITS = 30>
  6. struct xor_basis {
  7.     T basis[BITS];
  8.     int r = 0;
  9.  
  10.     xor_basis() {
  11.         for(int i = 0; i < BITS; i++) {
  12.             basis[i] = 0;
  13.         }
  14.     }
  15.  
  16.     bool insert(T x, int id = -1) {
  17.         if(contains(x)) return false;
  18.         for(int b = BITS - 1; b >= 0; b--) {
  19.             if(x >> b & 1) {
  20.                 if(basis[b]) {
  21.                     x ^= basis[b];
  22.                 } else {
  23.                     basis[b] = x;
  24.                     r++;
  25.                     return true;
  26.                 }
  27.             }
  28.         }
  29.         return false;
  30.     }
  31.    
  32.     bool contains(T x) const {
  33.         return min_value(x) == 0;
  34.     }
  35.  
  36.     T min_value(T x) const {
  37.         if(r == BITS) return 0;
  38.         for(int i = BITS - 1; i >= 0; i--) x = min(x, x ^ basis[i]);
  39.         return x;
  40.     }
  41.  
  42.     int reduce(T pref, int from_bit) const {
  43.         for(int b = BITS - 1; b >= from_bit; b--) {
  44.             if(pref >> b & 1 && basis[b]) {
  45.                 pref ^= basis[b];
  46.             }
  47.         }
  48.         return pref;
  49.     }
  50.  
  51.     int can_make_prefix(T ai, T pref, int from_bit) const {
  52.         T now = ai ^ pref;
  53.         T v = reduce(now, from_bit);
  54.         return (v >> from_bit) == 0;
  55.     }
  56.  
  57.     T max_value(T ai, T bi) const { // find maximum x <= bi such that ai ^ x exists
  58.         T x = 0;
  59.         T mx = ai <= bi ? ai : -1;
  60.         for(int i = BITS - 1; i >= 0; i--) {
  61.             int b_bit = bi >> i & 1;
  62.             if(can_make_prefix(ai, x, i)) {
  63.                 T pref = reduce(x ^ ai, i);
  64.                 T nx = x;
  65.                 for(int j = i - 1; j >= 0; j--) {
  66.                     int change = 0;
  67.                     if((nx | (1ll << j)) <= bi) {
  68.                         change = 1;
  69.                         nx |= 1ll << j;
  70.                         pref ^= 1ll << j;
  71.                     }
  72.                     if(pref >> j & 1) {
  73.                         if(basis[j]) {
  74.                             pref ^= basis[j];
  75.                         } else {
  76.                             pref ^= 1ll << j;
  77.                             nx ^= change << j;
  78.                         }
  79.                     }
  80.                 }
  81.                 if(can_make_prefix(ai, nx, 0)) {
  82.                     mx = max(mx, nx);
  83.                 }
  84.             }
  85.             if(b_bit) {
  86.                 x |= 1ll << i;
  87.                 if(!can_make_prefix(ai, x, i)) break;
  88.             }
  89.         }
  90.         return mx;
  91.     }
  92. };
  93.  
  94. void solve() {
  95.     int n; cin >> n;
  96.     vector<int> a(n);
  97.     for(auto& x : a) {
  98.         cin >> x;
  99.     }
  100.     xor_basis<int> xr;
  101.     xr.insert(a[n - 1]);
  102.     for(int i = n - 2; i >= 0; i--) {
  103.         int mx = xr.max_value(a[i], a[i + 1]);
  104.         if(mx == -1) {
  105.             cout << -1 << '\n';
  106.             return;
  107.         }
  108.         a[i] = mx;
  109.         xr.insert(a[i]);
  110.     }
  111.     for(int i = 0; i < n; i++) {
  112.         cout << a[i] << (i == n - 1 ? '\n' : ' ');
  113.     }
  114. }
  115.  
  116. signed main() {
  117.     IOS;
  118.     int t = 1;
  119.     cin >> t;
  120.     for(int i = 1; i <= t; i++) {  
  121.         //cout << "Case #" << i << ": ";  
  122.         solve();
  123.     }
  124.     return 0;
  125. }
  126.  
Advertisement
Add Comment
Please, Sign In to add comment