codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

92105.md (16301B)


      1 Source: https://codeforces.com/blog/entry/158572
      2 
      3 Thank you everyone for participating in the round! We hope you enjoyed the problems :)
      4 
      5 ### [2280A - Are They the Same?](/contest/2280/problem/A "Codeforces Round 1133 (Div. 2)")
      6 
      7 Problem author: [conqueror_of_tourist](/profile/conqueror_of_tourist "International Grandmaster conqueror_of_tourist")
      8 
      9 **Hint**
     10 
     11 What happens when $k$ is even? What happens when $k$ is odd?
     12 
     13 **Solution**
     14 
     15 Tutorial is loading...
     16 
     17 **Code**
     18 
     19 ```
     20 for _ in range(int(input())):
     21     n, k = list(map(int, input().split()))
     22     a = list(map(lambda x: int(x) % 2, input().split()))
     23     b = list(map(lambda x: int(x) % 2, input().split()))
     24  
     25     if k % 2 == 0:
     26         print("YES" if a.count(0) <= b.count(0) else "NO")
     27     else:
     28         print("YES" if b.count(0) <= a.count(0) else "NO")
     29 ```
     30 
     31 ### [2280B - Secret String Patterns](/contest/2280/problem/B "Codeforces Round 1133 (Div. 2)")
     32 
     33 Problem author: [applepi216](/profile/applepi216 "Master applepi216")
     34 
     35 **Hint**
     36 
     37 What must all strings whose answer is ``NO'' look like?
     38 
     39 **Solution**
     40 
     41 Tutorial is loading...
     42 
     43 **Code**
     44 
     45 ```
     46 import sys
     47  
     48 for _ in range(int(input())):
     49     n = int(input())
     50     print("?", 1, n)
     51     sys.stdout.flush()
     52     ct = int(input())
     53     if ct == 0:
     54         print("! NO")
     55         continue
     56     print("?", 1, ct)
     57     sys.stdout.flush()
     58     x = int(input())
     59     if x == ct:
     60         print("! NO")
     61     else:
     62         print("! YES")
     63 ```
     64 
     65 ### [2279A - Reverse and Double](/contest/2279/problem/A "Codeforces Round 1133 (Div. 1)")
     66 
     67 Problem author: [conqueror_of_tourist](/profile/conqueror_of_tourist "International Grandmaster conqueror_of_tourist")
     68 
     69 **Hint 1**
     70 
     71 Where is it useful to "cut" the array to decrease the gap value?
     72 
     73 **Hint 2**
     74 
     75 Consider separately the cases where the gap value is unique, occurs twice, and occurs three or more times.
     76 
     77 **Solution**
     78 
     79 Tutorial is loading...
     80 
     81 **Code**
     82 
     83 ```
     84 #include <bits/stdc++.h>
     85 using namespace std;
     86  
     87 template <class T, T (*f)(T, T), T (*unit)()> struct Seg {
     88 	vector<T> s; int n;
     89 	Seg(int n = 0, T def = unit()) : s(2*n, def), n(n) {}
     90 	void update(int pos, T val) {
     91 		for (s[pos += n] = val; pos /= 2;)
     92 			s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
     93 	}
     94 	T query(int b, int e) { // query [b, e)
     95 		T ra = unit(), rb = unit();
     96 		for (b += n, e += n; b < e; b /= 2, e /= 2) {
     97 			if (b % 2) ra = f(ra, s[b++]);
     98 			if (e % 2) rb = f(s[--e], rb);
     99 		}
    100 		return f(ra, rb);
    101 	}
    102  
    103 	T get(int x) { return s[x+n]; }
    104 };
    105  
    106 using T = int;
    107 T f(T a, T b) { return max(a, b); }
    108 T unit() { return 0; }
    109  
    110 int main() {
    111     cin.tie(0)->sync_with_stdio(0);
    112  
    113     int t; cin >> t;
    114     while (t--) {
    115         int n; cin >> n;
    116         vector<int> a(n);
    117         for (int i = 0; i < n; i++) cin >> a[i];
    118  
    119         Seg<T, f, unit> rmq(n - 1);
    120         vector<int> mx;
    121         int val = -1;
    122         for (int i = 0; i < n - 1; i++) {
    123             rmq.update(i, abs(a[i + 1] - a[i]));
    124             if (abs(a[i + 1] - a[i]) > val)
    125                 mx = {i}, val = abs(a[i + 1] - a[i]);
    126             else if (abs(a[i + 1] - a[i]) == val)
    127                 mx.push_back(i);
    128         }
    129  
    130         if (mx.size() >= 3) {
    131             cout << val << "\n";
    132             continue;
    133         }
    134  
    135         auto calc = [&](int i, int j) {
    136             int v2 = 2 * rmq.query(i, j);
    137             if (i > 0) v2 = max({v2, rmq.query(0, i - 1), abs(a[i - 1] - 2 * a[j])});
    138             if (j < n - 1) v2 = max({v2, rmq.query(j + 1, n - 1), abs(a[j + 1] - 2 * a[i])});
    139             return v2;
    140         };
    141  
    142         if (mx.size() == 2) {
    143             int i = mx[0], j = mx[1];
    144             cout << min(val, calc(i + 1, j)) << "\n";
    145             continue;
    146         }
    147  
    148         int i = mx[0];
    149         for (int j = 0; j <= i; j++) {
    150             val = min(val, calc(j, i));
    151         }
    152         for (int j = i + 1; j < n; j++) {
    153             val = min(val, calc(i + 1, j));
    154         }
    155  
    156         cout << val << "\n";
    157     }
    158 }
    159 ```
    160 
    161 ### [2279B - Balanced Subsets](/contest/2279/problem/B "Codeforces Round 1133 (Div. 1)")
    162 
    163 Problem author: [conqueror_of_tourist](/profile/conqueror_of_tourist "International Grandmaster conqueror_of_tourist")
    164 
    165 **Hint 1**
    166 
    167 Suppose that $|S|\ge 2$. Can you say anything about the *minimum* number of unstable elements in it?
    168 
    169 **Hint 2**
    170 
    171 Consider DP.
    172 
    173 **Solution**
    174 
    175 Tutorial is loading...
    176 
    177 **Code**
    178 
    179 ```
    180 #include <bits/stdc++.h>
    181 using namespace std;
    182  
    183 using ll = long long;
    184 #define rep(i, a, b) for(int i = a; i < (b); ++i)
    185 #define all(x) (x).begin(), (x).end()
    186 #define sz(x) (int)(x).size()
    187  
    188 const ll MOD = 998244353;
    189  
    190 mt19937 rng(time(0));
    191  
    192 int main() {
    193 	cin.tie(0)->sync_with_stdio(0);
    194  
    195 	int t; cin >> t;
    196 	while (t--) {
    197 		int n; cin >> n;
    198 		vector<int> a(n);
    199 		rep(i,0,n) cin >> a[i];
    200  
    201 		vector<bool> s;
    202 		s.push_back(true);
    203 		for (int i = 1; i < n; i++) {
    204 			if (a[i] == a[i - 1] + 1) {
    205 				s.push_back(1);
    206 			} else if (a[i] == a[i - 1] + 2) {
    207 				s.push_back(0); s.push_back(1);
    208 			} else {
    209 				s.push_back(0); s.push_back(0); s.push_back(1);
    210 			}
    211 		}
    212 		s.push_back(0);
    213  
    214 		int m = sz(s);
    215 		assert(m < 3 * n);
    216 		ll ans = (1ll * (n + 1) * n / 2) % MOD; // n + (n C 2)
    217 		vector<ll> dp1(m + 1, 1); // ((1110)|(110))*
    218 		vector<ll> dp2(m + 1, 0); // 10((1110)|(110))*
    219 		for (int i = 1; i < m; i++) {
    220 			if (s[i - 1]) dp2[i + 1] = 1;
    221 			if (i >= 2 && s[i - 1] && s[i - 2]) {
    222 				dp1[i + 1] += dp1[i - 2];
    223 				dp2[i + 1] += dp2[i - 2];
    224 			}
    225 			if (i >= 3 && s[i - 1] && s[i - 2] && s[i - 3]) {
    226 				dp1[i + 1] += dp1[i - 3];
    227 				dp2[i + 1] += dp2[i - 3];
    228 			}
    229 			dp1[i + 1] %= MOD;
    230 			dp2[i + 1] %= MOD;
    231 			ans += dp1[i + 1] - 1 + dp2[i + 1];
    232 		}
    233 		for (int i = 1; i < m; i++) {
    234 			if (s[i - 1]) { // can end in 10
    235 				ans += dp1[i - 1] + dp2[i - 1];
    236 			}
    237 		}
    238 		s.push_back(0); s.push_back(0);
    239 		// we've overcounted 2 * 10, 110, 101 substrings
    240 		for (int i = 0; i < m; i++) {
    241 			if (s[i]) ans -= 2;
    242 			if (s[i] && s[i + 1]) ans -= 1;
    243 			if (s[i] && s[i + 2]) ans -= 1;
    244 		}
    245  
    246 		cout << ((ans + MOD) % MOD) << "\n";
    247  
    248 	}
    249  
    250 }
    251 ```
    252 
    253 ### [2279C - Anti-Productive](/contest/2279/problem/C "Codeforces Round 1133 (Div. 1)")
    254 
    255 Problem author: [conqueror_of_tourist](/profile/conqueror_of_tourist "International Grandmaster conqueror_of_tourist")
    256 
    257 **Hint 1**
    258 
    259 What should the array look like after applying your operations? (Equivalently, what operations should you apply?)
    260 
    261 **Hint 2**
    262 
    263 Consider casing on the *second largest* element.
    264 
    265 **Solution**
    266 
    267 Tutorial is loading...
    268 
    269 **Code**
    270 
    271 ```
    272 #include <bits/stdc++.h>
    273 using namespace std;
    274  
    275 using ll = long long;
    276 #define rep(i, a, b) for(int i = a; i < (b); ++i)
    277 #define all(x) (x).begin(), (x).end()
    278  
    279 int main() {
    280 	cin.tie(0)->sync_with_stdio(0);
    281  
    282 	int t; cin >> t;
    283 	while (t--) {
    284 		int n; ll L; cin >> n >> L;
    285 		vector<ll> a(n);
    286 		rep(i,0,n) cin >> a[i];
    287 		sort(all(a));
    288 		if (L == 1) {
    289 			cout << accumulate(all(a), 0ll) - a[n - 1] << "\n";
    290 			continue;
    291 		}
    292 		if (a[n - 1] * a[n - 2] < L) {
    293 			cout << "0\n";
    294 			continue;
    295 		}
    296 		ll x = a[n - 1];
    297 		ll y = 1;
    298 		while ((y + 1) * (y + 1) < L) ++y;
    299 		int start = n - 2;
    300 		ll curr = 0;
    301  
    302 		auto mx = [&](ll z) {
    303 			if (z == 0) return 0ll;
    304 			return max(0ll, x - (L - 1) / z);
    305 		};
    306  
    307 		while (start >= 0 && a[start] >= y) {
    308 			curr += (a[start] - y);
    309 			--start;
    310 		}
    311 		ll ans = curr + mx(y);
    312 		--y;
    313 		for (; y >= 0; --y) {
    314 			curr += (n - 2 - start);
    315 			while (start >= 0 && a[start] >= y) --start;
    316 			ans = min(ans, curr + mx(y));
    317 		}
    318 		cout << ans << "\n";
    319 	}
    320 }
    321 ```
    322 
    323 ### [2279D - Meta Graph](/contest/2279/problem/D "Codeforces Round 1133 (Div. 1)")
    324 
    325 Problem author: [FlakeLCR](/profile/FlakeLCR "Master FlakeLCR")
    326 
    327 We apologize for the weak test data on this problem.
    328 
    329 **Hint 1**
    330 
    331 The graph is quite huge. Do you need all of it?
    332 
    333 **Hint 2**
    334 
    335 Try to show that you only need to keep around $O(m + n)$ edges while preserving the shortest path.
    336 
    337 **Solution**
    338 
    339 Tutorial is loading...
    340 
    341 **Code**
    342 
    343 ```
    344 #include <bits/stdc++.h>
    345 using namespace std;
    346  
    347 #define rep(i, a, b) for(int i = a; i < (b); ++i)
    348 #define all(x) (x).begin(), (x).end()
    349 #define sz(x) (int)(x).size()
    350  
    351 mt19937 rng(time(0));
    352  
    353 int main() {
    354 	cin.tie(0)->sync_with_stdio(0);
    355  
    356 	int t; cin >> t;
    357 	while (t--) {
    358 		int n, m; cin >> n >> m;
    359 		int w, x, y, z; cin >> w >> x >> y >> z; --w, --x, --y, --z;
    360 		vector<array<int, 2>> edges(m);
    361 		vector<array<int, 2>> v;
    362 		rep(i,0,n) {
    363 			v.push_back({w, i});
    364 			v.push_back({y, i});
    365 			v.push_back({i, i});
    366 		}
    367  
    368 		rep(i,0,m) {
    369 			int a, b; cin >> a >> b; --a, --b;
    370 			edges[i] = {a, b};
    371 			v.push_back({a, b});
    372 			v.push_back({b, a});
    373 		}
    374  
    375 		sort(all(v));
    376 		v.resize(unique(all(v)) - v.begin());
    377  
    378 		int N = sz(v);
    379  
    380 		auto find = [&](int i, int j) -> int {
    381 			return lower_bound(all(v), array{i, j}) - v.begin();
    382 		};
    383  
    384 		vector<vector<int>> h(N);
    385 		for (auto [a, b] : edges) {
    386 			int wa = find(w, a), wb = find(w, b),
    387 			    ya = find(y, a), yb = find(y, b),
    388 			    aa = find(a, a), ab = find(a, b),
    389 			    ba = find(b, a), bb = find(b, b);
    390  
    391 			for (auto [p1, p2] : vector{array{wa, wb}, {ya, yb}, {aa, ab}, {ba, bb}, {ab, ba}}) {
    392 				h[p1].push_back(p2);
    393 				h[p2].push_back(p1);
    394 			}
    395 		}
    396  
    397 		vector<int> dist(N, -1);
    398 		queue<pair<int, int>> q;
    399 		q.emplace(find(w, x), 0);
    400 		while (!q.empty()) {
    401 			auto [vtx, d] = q.front();
    402 			q.pop();
    403 			if (dist[vtx] >= 0) continue;
    404 			dist[vtx] = d;
    405 			for (auto a : h[vtx]) {
    406 				if (dist[a] < 0) q.emplace(a, d + 1);
    407 			}
    408 		}
    409  
    410 		cout << dist[find(y, z)] << "\n";
    411 	}
    412 }
    413 ```
    414 
    415 ### [2279E - Save Me!](/contest/2279/problem/E "Codeforces Round 1133 (Div. 1)")
    416 
    417 Problem author: [conqueror_of_tourist](/profile/conqueror_of_tourist "International Grandmaster conqueror_of_tourist")
    418 
    419 **Hint 1**
    420 
    421 Can you upper bound the answer?
    422 
    423 **Hint 2**
    424 
    425 The answer is at most $2\cdot 25 - 1 = 49$. Can you use this fact to construct a solution running in time $O(n\cdot 2^{49})$?
    426 
    427 **Hint 3**
    428 
    429 Please refer to the previous hint first. Can you make your solution faster to $O(n\cdot \varphi^{49})$?
    430 
    431 **Hint 4**
    432 
    433 Consider Meet In The Middle.
    434 
    435 **Solution**
    436 
    437 Tutorial is loading...
    438 
    439 **Code**
    440 
    441 ```
    442 #include <bits/stdc++.h>
    443 using namespace std;
    444  
    445 #define pb push_back
    446 #define eb emplace_back
    447 #define mp make_pair
    448 #define all(v) v.begin(), v.end()
    449 #define sz(v) (int)v.size()
    450 #define sq(a) ((a)*(a))
    451  
    452 #define per(i,a,b) for (int i = (b)-1; i >= a; i--)
    453 #define rep(i,a,b) for (int i=a; i<b; i++)
    454  
    455 #define FOR(i,a,b) for (int i=a; i<b; i++)
    456 #define F0R(i,a) for (int i=0; i<a; i++)
    457 #define ROF(i,a,b) for (int i = (b)-1; i >= a; i--)
    458 #define R0F(i,a) for (int i = (a)-1; i >= 0; i--)
    459  
    460 #define FAST ios::sync_with_stdio(0); cin.tie(0);
    461 #define finish(x) return cout << x << endl, 0;
    462 #define dbg(x) cerr << ">>> " << #x << " = " << x << endl;
    463 #define _ << " _ " <<
    464  
    465 #define ll long long
    466  
    467 template<class T> bool ckmin(T&a, T&b) { bool B = a > b; a = min(a,b); return B; }
    468 template<class T> bool ckmax(T&a, T&b) { bool B = a < b; a = max(a,b); return B; }
    469  
    470 typedef long double ld;
    471 typedef pair<int,int> pi;
    472 typedef pair<ld,ld> pld;
    473 typedef complex<ld> cd;
    474  
    475 typedef vector<int> vi;
    476 typedef vector<ld> vld;
    477 typedef vector<vector<int>> vvi;
    478  
    479 const ld PI = acos(-1.0);
    480 const ld EPS = 1e-7;
    481 const int MOD = 998244353;
    482  
    483 const int MX = 25;
    484 const int BIG = 100;
    485  
    486 void solve() {
    487   int n; cin >> n;
    488   vector<int> a(n);
    489   rep(i, 0, n) {
    490     cin >> a[i];
    491   }
    492   
    493   if (*min_element(all(a)) == 0) {
    494       cout << "0" << "\n";
    495       return;
    496   }
    497  
    498   vector<pair<int, int>> seen;
    499  
    500   auto left = [&](auto && self, int i, int cost, int v) {
    501     int op = v ^ a[i];
    502     seen.push_back({op, cost});
    503  
    504     if (i == 0) return;
    505     if (cost + 1 <= MX) {
    506       self(self, i - 1, cost + 1, op);
    507     }
    508  
    509     if (cost + 2 <= MX) {
    510       self(self, i - 1, cost + 2, v);
    511     }
    512   };
    513  
    514   int best = BIG;
    515  
    516   auto right = [&](auto && self, int i, int cost, int v) {
    517     int op = v ^ a[i];
    518  
    519     auto it = upper_bound(all(seen), mp(op, -1));
    520     if (it != seen.end()) {
    521       auto [u, v] = *it;
    522       if (u == op) best = min(best, cost + v - 1);
    523     }
    524  
    525     if (i + 1 == n) return;
    526     if (cost + 1 <= MX) {
    527       self(self, i + 1, cost + 1, op);
    528     }
    529  
    530     if (cost + 2 <= MX) {
    531       self(self, i + 1, cost + 2, v);
    532     }
    533   };
    534  
    535   if (n > MX) {
    536     best = 2 * MX - 1;
    537   }
    538  
    539   rep(i, 0, n - 1) {
    540     seen.clear();
    541     seen.reserve(514228);
    542  
    543     left(left, i, 1, 0);
    544     assert (sz(seen) <= 514228);
    545     sort(all(seen));
    546  
    547     right(right, i + 1, 1, 0);
    548   }
    549  
    550   if (best == BIG) best = -1;
    551   cout << best << endl;
    552 }
    553  
    554 int32_t main() { FAST
    555   int t;
    556   cin >> t;
    557  
    558   while (t--) solve();
    559  
    560   return 0;
    561 }
    562 ```
    563 
    564 ### [2279F - The Stones of Nim](/contest/2279/problem/F "Codeforces Round 1133 (Div. 1)")
    565 
    566 Problem author: [applepi216](/profile/applepi216 "Master applepi216")
    567 
    568 **Hint 1**
    569 
    570 Recall how one wins in Nim. Next, note that this problem essentially reduces to solving each prefix quickly.
    571 
    572 **Hint 2**
    573 
    574 This is, under the hood, a matroid problem. For each new value, try to construct an "exchange" graph using the matroid basis exchange property to determine if it's possible to insert the element.
    575 
    576 **Hint 3**
    577 
    578 Please refer to the previous hint first. It gives an $O(n^3\log^2 n)$ time algorithm. To improve this, consider if you need the full graph or if you can "thin" it.
    579 
    580 **Hint 4**
    581 
    582 Make sure your XOR basis operations are of optimal complexity.
    583 
    584 **Solution**
    585 
    586 Tutorial is loading...
    587 
    588 **Code**
    589 
    590 ```
    591 #include <bits/stdc++.h>
    592 using namespace std;
    593  
    594 constexpr int LOG = 14;
    595  
    596 struct xor_basis {
    597 	vector<int> inner;
    598 	vector<int> base;
    599 	vector<int> comb;
    600  
    601 	xor_basis(): base(LOG), comb(LOG) {}
    602  
    603 	int represent(int mask) {
    604 		int c = 0;
    605 		for (int i = 0; i < LOG; i++) {
    606 			if (!(mask & (1 << i))) continue;
    607 			if (!base[i]) return -1;
    608 			mask ^= base[i], c ^= comb[i];
    609 		}
    610 		return c;
    611 	}
    612  
    613 	bool independent(int mask) {
    614 		for (int i = 0; i < LOG; i++) {
    615 			if (!(mask & (1 << i))) continue;
    616 			if (!base[i]) return true;
    617 			mask ^= base[i];
    618 		}
    619 		return false;
    620 	}
    621  
    622 	void swap(int out, int in) {
    623 		int pos = find(inner.begin(), inner.end(), out) - inner.begin();
    624 		int c = represent(in);
    625 		inner[pos] = in;
    626 		for (int i = 0; i < LOG; i++) if (comb[i] >> pos & 1) comb[i] ^= c ^ (1 << pos);
    627 	}
    628  
    629 	bool insert(int mask) {
    630 		int sv = mask, c = 1 << inner.size();
    631 		for (int i = 0; i < LOG; i++) {
    632 			if (!(mask & (1 << i))) continue;
    633  
    634 			if (!base[i]) {
    635 				base[i] = mask, comb[i] = c, inner.push_back(sv);
    636 				return true;
    637 			}
    638 			mask ^= base[i], c ^= comb[i];
    639 		}
    640 		return false;
    641 	}
    642 };
    643  
    644 void solve() {
    645     int n; cin >> n;
    646 	vector<int> a(n), s(n);
    647 	for (int i = 0; i < n; i++) cin >> a[i];
    648  
    649 	vector<xor_basis> bases;
    650 	bases.emplace_back();
    651  
    652 	auto add = [&](int idx) {
    653 		for (int i = 0; i < bases.size(); i++) {
    654 	        if (bases[i].independent(s[idx])) {
    655 	            bases[i].insert(s[idx]); // special case
    656 	            return;
    657 	        }
    658 	    }
    659  
    660 		int N = 2*n + bases.size();
    661  
    662 		vector<int> smap(N, -1);
    663 		for (int i = 0; i < bases.size(); i++) for (auto x : bases[i].inner) smap[x - 1] = i;
    664 		for (int i = 0; i < bases.size(); i++) smap[i + 2*n] = i;
    665  
    666 		vector<int> par(N, -2);
    667 		vector<int> q;
    668 		q.push_back(s[idx] - 1); par[s[idx] - 1] = -1;
    669 		int found = -1;
    670 		for (int head = 0; head < q.size(); head++) {
    671 			int vtx = q[head];
    672  
    673             int x = vtx + 1, next_idx = (smap[vtx] + 1) % bases.size();
    674  
    675             if (x == s[idx] || bases.size() > 1) {
    676                 if (bases[next_idx].independent(x)) {
    677                     par[2 * n + next_idx] = vtx, found = 2 * n + next_idx;
    678                     break;
    679                 }
    680 				int z = bases[next_idx].represent(x);
    681 				for (int p = 0; p < bases[next_idx].inner.size(); p++) {
    682 					if (z >> p & 1) {
    683 						int y = bases[next_idx].inner[p] - 1;
    684 						if (par[y] == -2) par[y] = vtx, q.push_back(y);
    685 					}
    686 				}
    687             }
    688 		}
    689  
    690 		if (found < 0) { // easy case -- no path
    691 			bases.emplace_back();
    692 			bases.back().insert(s[idx]);
    693 			return;
    694 		} else {
    695 			int p = par[found];
    696 			assert(bases[smap[found]].insert(p + 1));
    697 			while (p + 1 != s[idx]) {
    698 				int prev = par[p];
    699 				bases[smap[p]].swap(p + 1, prev + 1);
    700 				p = prev;
    701 			}
    702 		}
    703 	};
    704  
    705 	auto print_sol = [&]() {
    706 		cout << bases.size() << "\n";
    707 		for (const auto& base : bases) {
    708 			cout << base.inner.size();
    709 			for (auto x : base.inner) {
    710 				cout << " " << x;
    711 			}
    712 			cout << "\n";
    713 		}
    714 	};
    715  
    716 	for (int i = 0; i < n; i++) {
    717 		int k = (i == 0 ? 0 : bases.size());
    718 		s[i] = a[i] ^ k;
    719 		add(i);
    720 	}
    721 	print_sol();
    722 }
    723  
    724 int main() {
    725 	cin.tie(0)->sync_with_stdio(0);
    726  
    727     int t; cin >> t;
    728     while (t--) solve();
    729 }
    730 ```