Thank you to everyone who participated! ↵
↵
We are sorry for the poor testcases on C1, along with C1 and C2's solutions being so similar to the recent Div3 E. ↵
↵
[problem:2263A]↵
↵
Author: [user:kondasujay2,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2263A]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void tc() {↵
int n; cin >> n;↵
int cnt = 0;↵
vector<int> a(n);↵
for(int i = 0; i < n; i++) {↵
cin >> a[i];↵
cnt += a[i];↵
}↵
if(cnt >= n - cnt) {↵
cout << "Bessie\n";↵
} else {↵
cout << "Elsie\n";↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2263B]↵
↵
Author: [user:sukon,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2263B]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
void solve() {↵
int n, k; cin >> n >> k;↵
if(n==3 && k==5) {↵
cout << "8 5 9\n6 3 7\n2 1 4";↵
return;↵
}↵
if(n==5 && k==5) {↵
cout << "16 14 17 15 3\n25 22 5 23 24\n8 1 9 6 7\n4 18 21 19 20\n12 10 13 2 11";↵
return;↵
}↵
↵
int x = k-n+1;↵
if(!(1 <= x && x <= n)) { cout << -1; return; }↵
vector<vector<int>> ans(n, vector<int>(n));↵
ans[0][0] = 1;↵
int on = 2;↵
for(int i = 1; i < x; i++) {↵
ans[0][i] = on; on++;↵
ans[i][0] = on; on++;↵
}↵
for(int i = x; i < n; i++) {↵
ans[i][i] = on; on++;↵
}↵
↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < n; j++) {↵
if(!ans[i][j]) {↵
ans[i][j] = on; on++;↵
}↵
}↵
}↵
↵
for(int j = 0; j < n; j++) {↵
if(j) cout << "\n";↵
for(auto &i : ans[j]) cout << i << " ";↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) {↵
solve();↵
if(t) cout << "\n";↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2263C1] / [problem:2262A1]↵
↵
Author: [user:CutSandstone,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2262A1]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void tc() {↵
int n; cin >> n;↵
vector<int> b(n + 1);↵
for(int i = 1; i <= n; i++) cin >> b[i];↵
vector<pair<int, int>> goodivs;↵
vector<pair<int, int>> badivs;↵
for(int i = 1; i <= n; i++) {↵
badivs.push_back({b[i] * i, (b[i] + 1) * i - 1});↵
for(int j = 0; j < b[i]; j++) {↵
goodivs.push_back({j * i, (j + 1) * i - 1});↵
}↵
}↵
vector<int> d(n + 1);↵
for(auto [l, r] : badivs) {↵
d[min(n, l)]++;↵
d[min(n, r + 1)]--;↵
}↵
int csm = 0;↵
vector<int> gnums;↵
for(int i = 0; i < n; i++) {↵
csm += d[i];↵
if(csm == 0) {↵
gnums.push_back(i);↵
}↵
}↵
cout << gnums.size() << endl;↵
for(int i : gnums) cout << i << " ";↵
cout << endl;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2263C2] / [problem:2262A2]↵
↵
Author: [user:kondasujay2,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2262A2]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int MOD = 1e9 + 7;↵
↵
void tc() {↵
int n; cin >> n;↵
vector<int> b(n + 1);↵
for(int i = 1; i <= n; i++) cin >> b[i];↵
vector<pair<int, int>> goodivs;↵
vector<pair<int, int>> badivs;↵
for(int i = 1; i <= n; i++) {↵
if(b[i] > (n - 1) / i + 1) {↵
cout << 0 << endl;↵
return;↵
}↵
badivs.push_back({b[i] * i, (b[i] + 1) * i - 1});↵
for(int j = 0; j < b[i]; j++) {↵
goodivs.push_back({j * i, (j + 1) * i - 1});↵
}↵
}↵
vector<int> d(n + 1);↵
for(auto [l, r] : badivs) {↵
d[min(n, l)]++;↵
d[min(n, r + 1)]--;↵
}↵
int csm = 0;↵
vector<int> gnums;↵
for(int i = 0; i < n; i++) {↵
csm += d[i];↵
if(csm == 0) {↵
gnums.push_back(i);↵
}↵
}↵
set<pair<int, int>> st;↵
sort(goodivs.begin(), goodivs.end(), [&] (pair<int, int> iv, pair<int, int> iv2) {↵
return iv.second - iv.first < iv2.second - iv2.first;↵
});↵
for(auto [l, r] : goodivs) {↵
auto it = st.lower_bound({l, 0});↵
if(it != st.end() && it->second <= r) {↵
continue;↵
}↵
st.insert({l, r});↵
}↵
↵
vector<pair<int, int>> impivs(st.begin(), st.end());↵
int l = 0, r = 0;↵
vector<int> dp(impivs.size() + 1);↵
dp[0] = 1;↵
int poss = 1;↵
for(int i : gnums) {↵
while(l < impivs.size() && impivs[l].second < i) {↵
poss += MOD - dp[l];↵
poss %= MOD;↵
l++;↵
}↵
while(r < impivs.size() && impivs[r].first <= i) r++;↵
dp[r] += poss;↵
dp[r] %= MOD;↵
poss += poss;↵
poss %= MOD;↵
}↵
cout << dp[impivs.size()] << endl;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2263D] / [problem:2262B]↵
↵
Author: [user:kondasujay2,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2262B]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
using ll = long long;↵
↵
struct BIT {↵
vector<ll> tr;↵
BIT(int n) : tr(n + 1) {}↵
void add(int k, ll x) {↵
while(k < tr.size()) {↵
tr[k] += x;↵
k += k&-k;↵
}↵
}↵
ll sum(int k) {↵
ll res = 0;↵
while(k > 0) {↵
res += tr[k];↵
k -= k&-k;↵
}↵
return res;↵
}↵
};↵
↵
void tc() {↵
int n; cin >> n;↵
vector<int> a(n), p(n);↵
for(int i = 0; i < n; i++) {↵
cin >> a[i];↵
}↵
for(int i = 0; i < n; i++) {↵
cin >> p[i]; p[i]--;↵
}↵
reverse(p.begin(), p.end());↵
BIT bit(n);↵
set<int> imp; ↵
vector<int> ans(n);↵
for(int i = 0; i < n; i++) {↵
int k = p[i];↵
auto it = imp.upper_bound(k);↵
int pimp;↵
if(it == imp.begin() || bit.sum(k) - bit.sum(*prev(it)) < a[k]) {↵
imp.insert(k);↵
pimp = k;↵
} else {↵
pimp = *prev(it);↵
}↵
bit.add(k + 1, a[k]);↵
while(imp.upper_bound(k) != imp.end()) {↵
int j = *imp.upper_bound(k);↵
if(bit.sum(j) - bit.sum(pimp) >= a[j]) {↵
imp.erase(j);↵
} else {↵
break;↵
}↵
}↵
ans[i] = imp.size() - 1;↵
}↵
reverse(ans.begin(), ans.end());↵
for(int i : ans) cout << i << " ";↵
cout << endl;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2263E] / [problem:2262C]↵
↵
Author: [user:kondasujay2,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2262C]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
using ll = long long;↵
↵
const int MOD = 1e9 + 7;↵
↵
void tc() {↵
int n; cin >> n;↵
vector<ll> a(n);↵
for(int i = 0; i < n; i++) cin >> a[i];↵
int k = n / 2;↵
↵
int val = 1;↵
for(int i = 1; i <= k; i++) {↵
val = (ll)i * val % MOD;↵
}↵
for(int i = 1; i <= k - (n % 2 == 0 ? 2 : 1); i++) {↵
val = (ll)i * val % MOD;↵
}↵
↵
set<ll> xposs;↵
xposs.insert(a[n - 1] - a[n - 2]);↵
xposs.insert(a[n - 1] - a[n - 3]);↵
↵
int ans = 0;↵
for(ll x : xposs) {↵
vector<ll> b;↵
for(int i = 0; i < k; i++) {↵
b.push_back(i * x);↵
}↵
for(int i = 0; i < n - k; i++) {↵
b.push_back(a[n - 1] - i * x);↵
}↵
sort(b.begin(), b.end());↵
if(a == b) {↵
ans += val;↵
if(ans >= MOD) ans -= MOD;↵
}↵
}↵
cout << ans << endl;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2263F] / [problem:2262D]↵
↵
Authors: [user:sukon,2026-09-12] & [user:kondasujay2,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2262D]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void tc() {↵
int n; cin >> n;↵
↵
vector<int> a(n), b(n);↵
for(int i = 0; i < n; i++) cin >> a[i], a[i]--;↵
for(int i = 0; i < n; i++) cin >> b[i], b[i]--;↵
↵
int badcnt = 0;↵
for(int i = 0; i < n; i++) {↵
badcnt += a[i] != b[i];↵
}↵
if(badcnt == 0) {↵
cout << "0 1\n";↵
return;↵
}↵
↵
// mark everything which will ever be reached↵
vector<bool> useful(n);↵
for(int i = 0; i < n; i++) {↵
if(a[i] == b[i]) continue;↵
int x = i;↵
while(!useful[x]) {↵
useful[x] = true;↵
x = b[x];↵
}↵
}↵
↵
// anything with b[i] == i once we reach we can't reach anything else, ↵
// at most one of them can exit↵
vector<int> ends;↵
for(int i = 0; i < n; i++) {↵
if(useful[i] && b[i] == i) ends.push_back(i);↵
}↵
↵
if(ends.size() > 1) {↵
cout << "-1\n";↵
return;↵
}↵
↵
vector<vector<int>> adj(n), radj(n);↵
for(int i = 0; i < n; i++) {↵
if(a[i] > b[i]) {↵
cout << "-1\n";↵
return;↵
}↵
for(int j = a[i]; j <= b[i]; j++) {↵
adj[i].push_back(j);↵
radj[j].push_back(i);↵
}↵
}↵
↵
// tarjan algorithm, from cp-algorithms↵
vector<int> st; // - stack holding the unclaimed vertices↵
vector<int> roots(n, -1); // - keeps track of the SCC roots of the vertices↵
int timer = 0; // - dfs timestamp counter↵
vector<int> t_in(n, -1); // - keeps track of the dfs timestamp of the vertices↵
vector<int> t_low(n, -1); // - keeps track of the lowest t_in of unclaimed vertices↵
// reachable in the subtree↵
↵
// implements the tarjan algorithm for strongly connected components↵
auto dfs = [&](auto&& self, int s) -> void {↵
t_low[s] = t_in[s] = timer++;↵
st.push_back(s);↵
↵
for (auto u : adj[s]) {↵
if (t_in[u] == -1) { // tree-edge↵
self(self, u);↵
t_low[s] = min(t_low[s], t_low[u]);↵
} else if (roots[u] == -1) { // back-edge, cross-edge or forward-edge to an unclaimed vertex↵
t_low[s] = min(t_low[s], t_in[u]);↵
}↵
}↵
↵
if (t_low[s] == t_in[s]) { // vertex is a root↵
while (true) {↵
int u = st.back();↵
st.pop_back();↵
roots[u] = s; // claims the vertex↵
if (u == s)↵
break;↵
}↵
}↵
};↵
↵
// applies the tarjan algorithm to all the vertices↵
for (int v = 0; v < n; v++) {↵
if (t_in[v] == -1) {↵
dfs(dfs, v);↵
}↵
}↵
vector<vector<int>> comps(n);↵
for(int v = 0; v < n; v++) {↵
comps[roots[v]].push_back(v);↵
}↵
↵
vector<int> p(n, -1);↵
vector<int> sz(n);↵
for(int i = 0; i < n; i++) {↵
if(a[i] != b[i]) {↵
sz[roots[i]]++;↵
}↵
if(useful[i] && roots[i] != roots[b[i]]) {↵
if(p[roots[b[i]]] != -1) {↵
cout << "-1\n";↵
return;↵
}↵
p[roots[b[i]]] = roots[i];↵
}↵
}↵
vector<int> chain;↵
int x = roots[ends[0]];↵
int csz = 0;↵
while(x != -1) {↵
chain.push_back(x);↵
csz += sz[x];↵
x = p[x];↵
}↵
if(csz != badcnt) {↵
cout << "-1\n";↵
return;↵
}↵
reverse(chain.begin(), chain.end());↵
↵
{↵
x = comps[chain[0]][0];↵
vector<int> ops;↵
auto op1 = [&] () {↵
ops.push_back(1);↵
a[x]++;↵
};↵
auto op2 = [&] () {↵
ops.push_back(2);↵
x = a[x];↵
};↵
auto solve_scc = [&] () {↵
int rt = roots[x];↵
vector<int> comp = comps[rt];↵
↵
vector<int> p2(n, -1);↵
// only one thing in comp case↵
auto rdfs = [&] (auto&& self, int s) -> void {↵
for(int u : radj[s]) {↵
if(roots[u] != rt) continue;↵
if(p2[u] == -1) {↵
p2[u] = s;↵
self(self, u);↵
}↵
}↵
};↵
↵
// root a tree↵
rdfs(rdfs, comp[0]);↵
↵
for(int i = 0; i < comp.size(); i++) {↵
while(x != comp[i]) {↵
while(a[x] < max(p2[x], comp[i])) op1();↵
op2();↵
}↵
while(a[x] < b[x]) op1();↵
op2();↵
}↵
};↵
for(int i = 0; i < chain.size(); i++) solve_scc();↵
↵
cout << ops.size() << " " << comps[chain[0]][0] + 1 << endl;↵
for(int i : ops) cout << i << " ";↵
cout << endl;↵
↵
for(int i = 0; i < n; i++) assert(a[i] == b[i]);↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Magic">↵
With this, you can prove a significantly simpler solution. We will add this proof later.↵
</spoiler>↵
↵
↵
<spoiler summary="Magic Solution">↵
↵
~~~~~↵
// Note: AI generated solution↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
↵
while (t--) {↵
int n;↵
cin >> n;↵
↵
vector<int> a(n + 1), b(n + 1);↵
for (int i = 1; i <= n; i++) {↵
cin >> a[i];↵
}↵
for (int i = 1; i <= n; i++) {↵
cin >> b[i];↵
}↵
↵
int start = 1, remaining = 0;↵
bool possible = true;↵
↵
for (int i = 1; i <= n; i++) {↵
if (a[i] > b[i]) {↵
possible = false;↵
}↵
if (a[i] < b[i]) {↵
if (remaining == 0) {↵
start = i;↵
}↵
remaining++;↵
}↵
}↵
↵
if (!possible) {↵
cout << -1 << '\n';↵
continue;↵
}↵
↵
vector<int> operations;↵
int position = start;↵
↵
while (remaining > 0) {↵
if (a[position] < b[position]) {↵
while (a[position] < b[position] &&↵
(a[position] >= position ||↵
a[a[position]] == b[a[position]])) {↵
a[position]++;↵
operations.push_back(1);↵
}↵
↵
if (a[position] == b[position]) {↵
remaining--;↵
}↵
}↵
↵
if (remaining == 0 || a[position] == position) {↵
break;↵
}↵
↵
operations.push_back(2);↵
position = a[position];↵
}↵
↵
if (remaining > 0) {↵
cout << -1 << '\n';↵
continue;↵
}↵
↵
cout << operations.size() << ' ' << start << '\n';↵
for (int operation : operations) {↵
cout << operation << ' ';↵
}↵
cout << '\n';↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2262E]↵
↵
Author: [user:kondasujay2,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2262E]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int MOD;↵
↵
void madd(int& a, int b) {↵
a += b;↵
if(a >= MOD) a -= MOD;↵
}↵
↵
void msub(int& a, int b) {↵
a -= b;↵
if(a < 0) a += MOD;↵
}↵
↵
int mmul(int a, int b) {↵
return 1LL * a * b % MOD;↵
}↵
↵
int bpow(int x, int y) {↵
return y == 0 ? 1 : mmul((y % 2) ? x : 1, bpow(mmul(x, x), y / 2));↵
}↵
↵
void tc() {↵
int n; cin >> n >> MOD;↵
vector<int> f(2 * n + 1), invf(2 * n + 1);↵
f[0] = 1;↵
for(int i = 1; i <= 2 * n; i++) {↵
f[i] = mmul(f[i - 1], i);↵
}↵
invf[2 * n] = bpow(f[2 * n], MOD - 2);↵
for(int i = 2 * n; i >= 1; i--) {↵
invf[i - 1] = mmul(invf[i], i);↵
}↵
auto F = [&] (int n, int k) -> int {↵
return mmul(f[n], mmul(invf[k + 1], invf[n - k]));↵
};↵
auto choose = [&] (int n, int k) -> int {↵
return mmul(f[n], mmul(invf[k], invf[n - k]));↵
};↵
vector<vector<int>> p(n + 1, vector<int>(n + 1));↵
for(int i = 0; i <= n; i++) {↵
p[0][i] = mmul(F(2 * i, i), F(2 * i, i));↵
}↵
for(int i = 1; i <= n; i++) {↵
for(int j = 0; j <= n; j++) {↵
for(int k = 0; j + k <= n; k++) {↵
madd(p[i][j + k], mmul(p[i - 1][j], p[0][k]));↵
}↵
}↵
}↵
vector<int> ans(n + 1);↵
for(int i = 0; i <= n; i++) {↵
ans[i] = mmul(F(2 * n, i), p[i][n - i]);↵
}↵
for(int i = n - 1; i >= 0; i--) {↵
for(int j = i + 1; j <= n; j++) {↵
msub(ans[i], mmul(ans[j], choose(j, i)));↵
}↵
}↵
for(int i = 0; i <= n; i++) {↵
cout << ans[i] << " ";↵
}↵
cout << endl;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t; ↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2262F]↵
↵
Authors: [user:sukon,2026-09-12] & [user:kondasujay2,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2262F]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int MXN = 400;↵
↵
template<size_t SZ> int compute_inv(const vector<bitset<SZ>>& mat, vector<bitset<SZ>>& inv) {↵
int n = mat.size();↵
vector<bool> empty(n, true);↵
vector<bitset<SZ>> basis(n);↵
↵
for(int i = 0; i < n; i++) {↵
bitset<SZ> cur = mat[i];↵
bitset<SZ> curinv;↵
curinv[i] = 1;↵
for(int j = 0; j < n; j++) {↵
if(cur[j]) {↵
if(empty[j]) {↵
basis[j] = cur;↵
inv[j] = curinv;↵
empty[j] = false;↵
break;↵
} else {↵
cur ^= basis[j];↵
curinv ^= inv[j];↵
}↵
}↵
}↵
}↵
for(int i = 0; i < n; i++) {↵
if(empty[i]) return 0;↵
}↵
↵
for(int i = n - 1; i >= 1; i--) {↵
for(int j = 0; j < i; j++) {↵
if(basis[j][i]) {↵
basis[j] ^= basis[i];↵
inv[j] ^= inv[i];↵
}↵
}↵
}↵
return 1;↵
}↵
↵
bool try_removal(vector<pair<int, int>> cells, vector<bitset<MXN>>& mat, vector<bitset<MXN>>& inv, vector<int>& row_cnt) {↵
int n = mat.size(), k = cells.size();↵
for(auto [x, y] : cells) {↵
if(mat[x][y] == 0) {↵
return false;↵
}↵
}↵
assert(k < 4);↵
vector<bitset<3>> K(k); ↵
for(int i = 0; i < k; i++) {↵
for(int j = 0; j < k; j++) {↵
K[i][j] = (i == j) ^ inv[cells[i].second][cells[j].first];↵
}↵
}↵
vector<bitset<3>> invK(cells.size());↵
if(!compute_inv(K, invK)) {↵
return false;↵
}↵
for(auto [x, y] : cells) {↵
mat[x][y] = 0;↵
row_cnt[x]--;↵
}↵
↵
auto old = inv;↵
for(int i = 0; i < n; i++) {↵
bitset<3> coef;↵
for(int alpha = 0; alpha < k; alpha++) {↵
int r = cells[alpha].first;↵
↵
if(old[i][r]) {↵
coef ^= invK[alpha];↵
}↵
}↵
↵
// delta = coef * (V^T * old)↵
for(int beta = 0; beta < k; beta++) {↵
if(coef[beta]) {↵
int c = cells[beta].second;↵
inv[i] ^= old[c];↵
}↵
}↵
}↵
return true;↵
}↵
↵
vector<int> compute_matching(const vector<bitset<MXN>>& mat) {↵
int n = mat.size();↵
vector<vector<int>> adj(n);↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < n; j++) {↵
if(mat[i][j]) adj[i].push_back(j);↵
}↵
}↵
↵
vector<int> match(n, -1);↵
vector<bool> done(n);↵
↵
function<bool(int)> dfs = [&] (int s) {↵
for(int u : adj[s]) {↵
if(!done[u]) {↵
done[u] = true;↵
↵
if(match[u] == -1 || dfs(match[u])) {↵
match[u] = s;↵
return true;↵
}↵
}↵
}↵
return false;↵
};↵
↵
for(int i = 0; i < n; i++) {↵
fill(done.begin(), done.end(), false);↵
dfs(i);↵
}↵
↵
for(int i = 0; i < n; i++) {↵
assert(match[i] != -1);↵
}↵
return match;↵
}↵
↵
void tc() {↵
int n, m; cin >> n >> m;↵
↵
vector<bitset<MXN>> mat(n);↵
vector<int> row_cnt(n);↵
for(int i = 0; i < m; i++) {↵
int x, y; cin >> x >> y;↵
x--, y--;↵
mat[x][y] = 1;↵
row_cnt[x]++;↵
}↵
↵
vector<bitset<MXN>> inv(n);↵
compute_inv(mat, inv);↵
↵
int sm = m;↵
int left = (sm + n - 1) / n;↵
cout << left << '\n';↵
↵
while(sm > 0) {↵
vector<bitset<MXN>> omat = mat;↵
if(sm <= n) {↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < n; j++) {↵
mat[i][j] = 0;↵
}↵
}↵
row_cnt.assign(n, 0);↵
} else if(sm <= 2 * n) {↵
vector<int> matching = compute_matching(mat);↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < n; j++) {↵
mat[i][j] = 0;↵
}↵
}↵
row_cnt.assign(n, 0);↵
for(int i = 0; i < sm - n; i++) {↵
mat[matching[i]][i] = 1;↵
row_cnt[matching[i]]++;↵
}↵
} else if(sm <= 3 * n) {↵
vector<int> matching = compute_matching(mat);↵
int above = 0;↵
for(int i = 0; i < n; i++) {↵
for(int j = matching[i] + 1; j < n; j++) {↵
above += mat[j][i];↵
}↵
}↵
↵
vector<bitset<MXN>> nmat(n);↵
vector<int> nrow_cnt(n);↵
int ones_left = sm - n;↵
for(int i = 0; i < n; i++) {↵
nmat[matching[i]][i] = 1;↵
nrow_cnt[matching[i]]++;↵
ones_left--;↵
}↵
// make matrix either upper or lower triangular, whichever one↵
// removes a sufficient number of ones↵
if(above >= ones_left) {↵
for(int i = 0; i < n; i++) {↵
for(int j = matching[i] + 1; j < n; j++) {↵
if(mat[j][i]) {↵
ones_left--;↵
nmat[j][i] = 1;↵
nrow_cnt[j]++;↵
if(ones_left == 0) break;↵
}↵
}↵
if(ones_left == 0) break;↵
}↵
} else {↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < matching[i]; j++) {↵
if(mat[j][i]) {↵
ones_left--;↵
nmat[j][i] = 1;↵
nrow_cnt[j]++;↵
if(ones_left == 0) break;↵
}↵
}↵
if(ones_left == 0) break;↵
}↵
}↵
mat = nmat;↵
row_cnt = nrow_cnt;↵
} else {↵
int csm = sm;↵
if(n % 2) {↵
// odd case (remove either 1 or 3)↵
int dup_row = -1;↵
for(int i = 0; i < n; i++) {↵
if(row_cnt[i] >= 2) {↵
dup_row = i;↵
break;↵
}↵
}↵
assert(dup_row != -1);↵
↵
vector<int> cols;↵
for(int i = 0; i < n; i++) {↵
if(mat[dup_row][i]) cols.push_back(i);↵
}↵
↵
assert(cols.size() >= 2);↵
↵
for(int i = 0; i < n; i++) {↵
if(try_removal({{i, cols[0]}}, mat, inv, row_cnt)) {↵
csm--;↵
break;↵
}↵
if(try_removal({{i, cols[1]}}, mat, inv, row_cnt)) {↵
csm--;↵
break;↵
}↵
}↵
↵
if(csm == sm) {↵
for(int i = 0; i < n; i++) {↵
if(i != dup_row) {↵
// remove L shape↵
if(try_removal(↵
{{i, cols[0]}, ↵
{dup_row, cols[0]}, ↵
{dup_row, cols[1]}},↵
mat, inv, row_cnt)) {↵
csm -= 3;↵
break;↵
}↵
}↵
}↵
assert(sm != csm);↵
}↵
}↵
↵
while(csm > sm - n) {↵
// remove 2 at a time↵
int dup_row = -1;↵
for(int i = 0; i < n; i++) {↵
if(row_cnt[i] >= 3) {↵
dup_row = i;↵
break;↵
}↵
}↵
↵
vector<int> cols;↵
for(int i = 0; i < n; i++) {↵
if(mat[dup_row][i]) cols.push_back(i);↵
}↵
↵
assert(cols.size() >= 3);↵
↵
if(!try_removal({{dup_row, cols[0]}, {dup_row, cols[1]}}, mat, inv, row_cnt)) {↵
if(!try_removal({{dup_row, cols[1]}, {dup_row, cols[2]}}, mat, inv, row_cnt)) {↵
if(!try_removal({{dup_row, cols[0]}, {dup_row, cols[2]}}, mat, inv, row_cnt)) {↵
assert(false);↵
}↵
}↵
}↵
↵
csm -= 2;↵
}↵
assert(csm == sm - n);↵
}↵
↵
vector<pair<int, int>> move;↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < n; j++) {↵
if(omat[i][j] == 1 && mat[i][j] == 0) {↵
move.push_back({i, j});↵
}↵
}↵
}↵
cout << move.size() << "\n";↵
for(auto [x, y] : move) cout << x + 1 << " " << y + 1 << "\n";↵
sm -= n;↵
↵
int csm = 0;↵
for(int i = 0; i < n; i++) {↵
csm += row_cnt[i];↵
}↵
assert(csm == max(0, sm));↵
}↵
}↵
↵
int main() {↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Tester Solution">↵
Will be added later; credit to [user:BurnedChicken,2026-09-10] for finding this in testing!↵
This method results in a much simpler solution!↵
</spoiler>↵
↵
↵
<spoiler>↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int SZ = 400;↵
↵
↵
template<size_t SZ> int compute_inv(const vector<bitset<SZ>>& mat, vector<bitset<SZ>>& inv) {↵
int n = mat.size();↵
vector<bool> empty(n, true);↵
vector<bitset<SZ>> basis(n);↵
↵
for(int i = 0; i < n; i++) {↵
bitset<SZ> cur = mat[i];↵
bitset<SZ> curinv;↵
curinv[i] = 1;↵
for(int j = 0; j < n; j++) {↵
if(cur[j]) {↵
if(empty[j]) {↵
basis[j] = cur;↵
inv[j] = curinv;↵
empty[j] = false;↵
break;↵
} else {↵
cur ^= basis[j];↵
curinv ^= inv[j];↵
}↵
}↵
}↵
}↵
for(int i = 0; i < n; i++) {↵
if(empty[i]) return 0;↵
}↵
↵
for(int i = n - 1; i >= 1; i--) {↵
for(int j = 0; j < i; j++) {↵
if(basis[j][i]) {↵
basis[j] ^= basis[i];↵
inv[j] ^= inv[i];↵
}↵
}↵
}↵
return 1;↵
}↵
↵
void tc() {↵
int n, m; cin >> n >> m;↵
vector<bitset<SZ>> mat(n);↵
for(int i = 0; i < m; i++) {↵
int x, y; cin >> x >> y;↵
x--, y--;↵
mat[x][y] = 1;↵
}↵
↵
vector<bitset<SZ>> inv(n);↵
compute_inv(mat, inv);↵
vector<int> cnts(2 * n);↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < n; j++) {↵
cnts[i] += mat[i][j];↵
cnts[n + j] += mat[i][j];↵
}↵
}↵
queue<pair<int, int>> mustq, freeq;↵
vector<pair<int, int>> centers;↵
vector<vector<pair<int, int>>> moves;↵
while(true) {↵
while(mustq.size() + freeq.size() < n) {↵
int best_rc = 0;↵
for(int rc = 0; rc < 2 * n; rc++) {↵
if(cnts[rc] >= cnts[best_rc]) best_rc = rc;↵
}↵
if(cnts[best_rc] == 0) {↵
break;↵
}↵
↵
int x = -1, y = -1;↵
if(best_rc < n) {↵
x = best_rc;↵
for(int j = 0; j < n; j++) {↵
if(mat[x][j] && inv[j][x]) {↵
y = j;↵
break;↵
}↵
}↵
} else {↵
y = best_rc - n;↵
for(int j = 0; j < n; j++) {↵
if(mat[j][y] && inv[y][j]) {↵
x = j;↵
break;↵
}↵
}↵
}↵
assert(x != -1 && y != -1);↵
↵
centers.push_back({x, y});↵
vector<pair<int, int>> must, free;↵
auto erase = [&] (int a, int b) {↵
mat[a][b] = 0;↵
cnts[a]--;↵
cnts[b + n]--;↵
};↵
for(int j = 0; j < n; j++) {↵
if(mat[x][j] && j != y) {↵
must.push_back({x, j});↵
erase(x, j);↵
}↵
}↵
for(int j = 0; j < n; j++) {↵
if(mat[j][y] && j != x) {↵
free.push_back({j, y});↵
erase(j, y);↵
}↵
}↵
erase(x, y);↵
assert(cnts[x] == 0 && cnts[n + y] == 0);↵
↵
if(best_rc < n) swap(must, free);↵
for(auto u : must) mustq.push(u);↵
for(auto u : free) freeq.push(u);↵
↵
bitset<SZ> row = inv[y];↵
for(int j = 0; j < n; j++) {↵
if(cnts[j + n] > 0 && inv[j][x]) {↵
inv[j] ^= row;↵
}↵
}↵
}↵
int left = n;↵
vector<pair<int, int>> move;↵
while(left > 0 && mustq.size() > 0) {↵
left--;↵
move.push_back(mustq.front());↵
mustq.pop();↵
}↵
while(left > 0 && freeq.size() > 0) {↵
left--;↵
move.push_back(freeq.front());↵
freeq.pop();↵
}↵
while(left > 0 && centers.size() > 0) {↵
left--;↵
move.push_back(centers.back());↵
centers.pop_back();↵
}↵
moves.push_back(move);↵
if(centers.size() == 0) break;↵
}↵
cout << moves.size() << "\n";↵
for(auto move : moves) {↵
cout << move.size() << "\n";↵
for(auto [u, v] : move) cout << u + 1 << " " << v + 1 << "\n";↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
↵
We are sorry for the poor testcases on C1, along with C1 and C2's solutions being so similar to the recent Div3 E. ↵
↵
[problem:2263A]↵
↵
Author: [user:kondasujay2,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2263A]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void tc() {↵
int n; cin >> n;↵
int cnt = 0;↵
vector<int> a(n);↵
for(int i = 0; i < n; i++) {↵
cin >> a[i];↵
cnt += a[i];↵
}↵
if(cnt >= n - cnt) {↵
cout << "Bessie\n";↵
} else {↵
cout << "Elsie\n";↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2263B]↵
↵
Author: [user:sukon,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2263B]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include<bits/stdc++.h>↵
↵
using namespace std;↵
↵
void solve() {↵
int n, k; cin >> n >> k;↵
if(n==3 && k==5) {↵
cout << "8 5 9\n6 3 7\n2 1 4";↵
return;↵
}↵
if(n==5 && k==5) {↵
cout << "16 14 17 15 3\n25 22 5 23 24\n8 1 9 6 7\n4 18 21 19 20\n12 10 13 2 11";↵
return;↵
}↵
↵
int x = k-n+1;↵
if(!(1 <= x && x <= n)) { cout << -1; return; }↵
vector<vector<int>> ans(n, vector<int>(n));↵
ans[0][0] = 1;↵
int on = 2;↵
for(int i = 1; i < x; i++) {↵
ans[0][i] = on; on++;↵
ans[i][0] = on; on++;↵
}↵
for(int i = x; i < n; i++) {↵
ans[i][i] = on; on++;↵
}↵
↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < n; j++) {↵
if(!ans[i][j]) {↵
ans[i][j] = on; on++;↵
}↵
}↵
}↵
↵
for(int j = 0; j < n; j++) {↵
if(j) cout << "\n";↵
for(auto &i : ans[j]) cout << i << " ";↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) {↵
solve();↵
if(t) cout << "\n";↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2263C1] / [problem:2262A1]↵
↵
Author: [user:CutSandstone,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2262A1]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void tc() {↵
int n; cin >> n;↵
vector<int> b(n + 1);↵
for(int i = 1; i <= n; i++) cin >> b[i];↵
vector<pair<int, int>> goodivs;↵
vector<pair<int, int>> badivs;↵
for(int i = 1; i <= n; i++) {↵
badivs.push_back({b[i] * i, (b[i] + 1) * i - 1});↵
for(int j = 0; j < b[i]; j++) {↵
goodivs.push_back({j * i, (j + 1) * i - 1});↵
}↵
}↵
vector<int> d(n + 1);↵
for(auto [l, r] : badivs) {↵
d[min(n, l)]++;↵
d[min(n, r + 1)]--;↵
}↵
int csm = 0;↵
vector<int> gnums;↵
for(int i = 0; i < n; i++) {↵
csm += d[i];↵
if(csm == 0) {↵
gnums.push_back(i);↵
}↵
}↵
cout << gnums.size() << endl;↵
for(int i : gnums) cout << i << " ";↵
cout << endl;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2263C2] / [problem:2262A2]↵
↵
Author: [user:kondasujay2,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2262A2]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int MOD = 1e9 + 7;↵
↵
void tc() {↵
int n; cin >> n;↵
vector<int> b(n + 1);↵
for(int i = 1; i <= n; i++) cin >> b[i];↵
vector<pair<int, int>> goodivs;↵
vector<pair<int, int>> badivs;↵
for(int i = 1; i <= n; i++) {↵
if(b[i] > (n - 1) / i + 1) {↵
cout << 0 << endl;↵
return;↵
}↵
badivs.push_back({b[i] * i, (b[i] + 1) * i - 1});↵
for(int j = 0; j < b[i]; j++) {↵
goodivs.push_back({j * i, (j + 1) * i - 1});↵
}↵
}↵
vector<int> d(n + 1);↵
for(auto [l, r] : badivs) {↵
d[min(n, l)]++;↵
d[min(n, r + 1)]--;↵
}↵
int csm = 0;↵
vector<int> gnums;↵
for(int i = 0; i < n; i++) {↵
csm += d[i];↵
if(csm == 0) {↵
gnums.push_back(i);↵
}↵
}↵
set<pair<int, int>> st;↵
sort(goodivs.begin(), goodivs.end(), [&] (pair<int, int> iv, pair<int, int> iv2) {↵
return iv.second - iv.first < iv2.second - iv2.first;↵
});↵
for(auto [l, r] : goodivs) {↵
auto it = st.lower_bound({l, 0});↵
if(it != st.end() && it->second <= r) {↵
continue;↵
}↵
st.insert({l, r});↵
}↵
↵
vector<pair<int, int>> impivs(st.begin(), st.end());↵
int l = 0, r = 0;↵
vector<int> dp(impivs.size() + 1);↵
dp[0] = 1;↵
int poss = 1;↵
for(int i : gnums) {↵
while(l < impivs.size() && impivs[l].second < i) {↵
poss += MOD - dp[l];↵
poss %= MOD;↵
l++;↵
}↵
while(r < impivs.size() && impivs[r].first <= i) r++;↵
dp[r] += poss;↵
dp[r] %= MOD;↵
poss += poss;↵
poss %= MOD;↵
}↵
cout << dp[impivs.size()] << endl;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2263D] / [problem:2262B]↵
↵
Author: [user:kondasujay2,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2262B]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
using ll = long long;↵
↵
struct BIT {↵
vector<ll> tr;↵
BIT(int n) : tr(n + 1) {}↵
void add(int k, ll x) {↵
while(k < tr.size()) {↵
tr[k] += x;↵
k += k&-k;↵
}↵
}↵
ll sum(int k) {↵
ll res = 0;↵
while(k > 0) {↵
res += tr[k];↵
k -= k&-k;↵
}↵
return res;↵
}↵
};↵
↵
void tc() {↵
int n; cin >> n;↵
vector<int> a(n), p(n);↵
for(int i = 0; i < n; i++) {↵
cin >> a[i];↵
}↵
for(int i = 0; i < n; i++) {↵
cin >> p[i]; p[i]--;↵
}↵
reverse(p.begin(), p.end());↵
BIT bit(n);↵
set<int> imp; ↵
vector<int> ans(n);↵
for(int i = 0; i < n; i++) {↵
int k = p[i];↵
auto it = imp.upper_bound(k);↵
int pimp;↵
if(it == imp.begin() || bit.sum(k) - bit.sum(*prev(it)) < a[k]) {↵
imp.insert(k);↵
pimp = k;↵
} else {↵
pimp = *prev(it);↵
}↵
bit.add(k + 1, a[k]);↵
while(imp.upper_bound(k) != imp.end()) {↵
int j = *imp.upper_bound(k);↵
if(bit.sum(j) - bit.sum(pimp) >= a[j]) {↵
imp.erase(j);↵
} else {↵
break;↵
}↵
}↵
ans[i] = imp.size() - 1;↵
}↵
reverse(ans.begin(), ans.end());↵
for(int i : ans) cout << i << " ";↵
cout << endl;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2263E] / [problem:2262C]↵
↵
Author: [user:kondasujay2,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2262C]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
using ll = long long;↵
↵
const int MOD = 1e9 + 7;↵
↵
void tc() {↵
int n; cin >> n;↵
vector<ll> a(n);↵
for(int i = 0; i < n; i++) cin >> a[i];↵
int k = n / 2;↵
↵
int val = 1;↵
for(int i = 1; i <= k; i++) {↵
val = (ll)i * val % MOD;↵
}↵
for(int i = 1; i <= k - (n % 2 == 0 ? 2 : 1); i++) {↵
val = (ll)i * val % MOD;↵
}↵
↵
set<ll> xposs;↵
xposs.insert(a[n - 1] - a[n - 2]);↵
xposs.insert(a[n - 1] - a[n - 3]);↵
↵
int ans = 0;↵
for(ll x : xposs) {↵
vector<ll> b;↵
for(int i = 0; i < k; i++) {↵
b.push_back(i * x);↵
}↵
for(int i = 0; i < n - k; i++) {↵
b.push_back(a[n - 1] - i * x);↵
}↵
sort(b.begin(), b.end());↵
if(a == b) {↵
ans += val;↵
if(ans >= MOD) ans -= MOD;↵
}↵
}↵
cout << ans << endl;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2263F] / [problem:2262D]↵
↵
Authors: [user:sukon,2026-09-12] & [user:kondasujay2,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2262D]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void tc() {↵
int n; cin >> n;↵
↵
vector<int> a(n), b(n);↵
for(int i = 0; i < n; i++) cin >> a[i], a[i]--;↵
for(int i = 0; i < n; i++) cin >> b[i], b[i]--;↵
↵
int badcnt = 0;↵
for(int i = 0; i < n; i++) {↵
badcnt += a[i] != b[i];↵
}↵
if(badcnt == 0) {↵
cout << "0 1\n";↵
return;↵
}↵
↵
// mark everything which will ever be reached↵
vector<bool> useful(n);↵
for(int i = 0; i < n; i++) {↵
if(a[i] == b[i]) continue;↵
int x = i;↵
while(!useful[x]) {↵
useful[x] = true;↵
x = b[x];↵
}↵
}↵
↵
// anything with b[i] == i once we reach we can't reach anything else, ↵
// at most one of them can exit↵
vector<int> ends;↵
for(int i = 0; i < n; i++) {↵
if(useful[i] && b[i] == i) ends.push_back(i);↵
}↵
↵
if(ends.size() > 1) {↵
cout << "-1\n";↵
return;↵
}↵
↵
vector<vector<int>> adj(n), radj(n);↵
for(int i = 0; i < n; i++) {↵
if(a[i] > b[i]) {↵
cout << "-1\n";↵
return;↵
}↵
for(int j = a[i]; j <= b[i]; j++) {↵
adj[i].push_back(j);↵
radj[j].push_back(i);↵
}↵
}↵
↵
// tarjan algorithm, from cp-algorithms↵
vector<int> st; // - stack holding the unclaimed vertices↵
vector<int> roots(n, -1); // - keeps track of the SCC roots of the vertices↵
int timer = 0; // - dfs timestamp counter↵
vector<int> t_in(n, -1); // - keeps track of the dfs timestamp of the vertices↵
vector<int> t_low(n, -1); // - keeps track of the lowest t_in of unclaimed vertices↵
// reachable in the subtree↵
↵
// implements the tarjan algorithm for strongly connected components↵
auto dfs = [&](auto&& self, int s) -> void {↵
t_low[s] = t_in[s] = timer++;↵
st.push_back(s);↵
↵
for (auto u : adj[s]) {↵
if (t_in[u] == -1) { // tree-edge↵
self(self, u);↵
t_low[s] = min(t_low[s], t_low[u]);↵
} else if (roots[u] == -1) { // back-edge, cross-edge or forward-edge to an unclaimed vertex↵
t_low[s] = min(t_low[s], t_in[u]);↵
}↵
}↵
↵
if (t_low[s] == t_in[s]) { // vertex is a root↵
while (true) {↵
int u = st.back();↵
st.pop_back();↵
roots[u] = s; // claims the vertex↵
if (u == s)↵
break;↵
}↵
}↵
};↵
↵
// applies the tarjan algorithm to all the vertices↵
for (int v = 0; v < n; v++) {↵
if (t_in[v] == -1) {↵
dfs(dfs, v);↵
}↵
}↵
vector<vector<int>> comps(n);↵
for(int v = 0; v < n; v++) {↵
comps[roots[v]].push_back(v);↵
}↵
↵
vector<int> p(n, -1);↵
vector<int> sz(n);↵
for(int i = 0; i < n; i++) {↵
if(a[i] != b[i]) {↵
sz[roots[i]]++;↵
}↵
if(useful[i] && roots[i] != roots[b[i]]) {↵
if(p[roots[b[i]]] != -1) {↵
cout << "-1\n";↵
return;↵
}↵
p[roots[b[i]]] = roots[i];↵
}↵
}↵
vector<int> chain;↵
int x = roots[ends[0]];↵
int csz = 0;↵
while(x != -1) {↵
chain.push_back(x);↵
csz += sz[x];↵
x = p[x];↵
}↵
if(csz != badcnt) {↵
cout << "-1\n";↵
return;↵
}↵
reverse(chain.begin(), chain.end());↵
↵
{↵
x = comps[chain[0]][0];↵
vector<int> ops;↵
auto op1 = [&] () {↵
ops.push_back(1);↵
a[x]++;↵
};↵
auto op2 = [&] () {↵
ops.push_back(2);↵
x = a[x];↵
};↵
auto solve_scc = [&] () {↵
int rt = roots[x];↵
vector<int> comp = comps[rt];↵
↵
vector<int> p2(n, -1);↵
// only one thing in comp case↵
auto rdfs = [&] (auto&& self, int s) -> void {↵
for(int u : radj[s]) {↵
if(roots[u] != rt) continue;↵
if(p2[u] == -1) {↵
p2[u] = s;↵
self(self, u);↵
}↵
}↵
};↵
↵
// root a tree↵
rdfs(rdfs, comp[0]);↵
↵
for(int i = 0; i < comp.size(); i++) {↵
while(x != comp[i]) {↵
while(a[x] < max(p2[x], comp[i])) op1();↵
op2();↵
}↵
while(a[x] < b[x]) op1();↵
op2();↵
}↵
};↵
for(int i = 0; i < chain.size(); i++) solve_scc();↵
↵
cout << ops.size() << " " << comps[chain[0]][0] + 1 << endl;↵
for(int i : ops) cout << i << " ";↵
cout << endl;↵
↵
for(int i = 0; i < n; i++) assert(a[i] == b[i]);↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
<spoiler summary="Magic">↵
With this, you can prove a significantly simpler solution. We will add this proof later.↵
</spoiler>↵
↵
↵
<spoiler summary="Magic Solution">↵
↵
~~~~~↵
// Note: AI generated solution↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
↵
while (t--) {↵
int n;↵
cin >> n;↵
↵
vector<int> a(n + 1), b(n + 1);↵
for (int i = 1; i <= n; i++) {↵
cin >> a[i];↵
}↵
for (int i = 1; i <= n; i++) {↵
cin >> b[i];↵
}↵
↵
int start = 1, remaining = 0;↵
bool possible = true;↵
↵
for (int i = 1; i <= n; i++) {↵
if (a[i] > b[i]) {↵
possible = false;↵
}↵
if (a[i] < b[i]) {↵
if (remaining == 0) {↵
start = i;↵
}↵
remaining++;↵
}↵
}↵
↵
if (!possible) {↵
cout << -1 << '\n';↵
continue;↵
}↵
↵
vector<int> operations;↵
int position = start;↵
↵
while (remaining > 0) {↵
if (a[position] < b[position]) {↵
while (a[position] < b[position] &&↵
(a[position] >= position ||↵
a[a[position]] == b[a[position]])) {↵
a[position]++;↵
operations.push_back(1);↵
}↵
↵
if (a[position] == b[position]) {↵
remaining--;↵
}↵
}↵
↵
if (remaining == 0 || a[position] == position) {↵
break;↵
}↵
↵
operations.push_back(2);↵
position = a[position];↵
}↵
↵
if (remaining > 0) {↵
cout << -1 << '\n';↵
continue;↵
}↵
↵
cout << operations.size() << ' ' << start << '\n';↵
for (int operation : operations) {↵
cout << operation << ' ';↵
}↵
cout << '\n';↵
}↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2262E]↵
↵
Author: [user:kondasujay2,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2262E]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int MOD;↵
↵
void madd(int& a, int b) {↵
a += b;↵
if(a >= MOD) a -= MOD;↵
}↵
↵
void msub(int& a, int b) {↵
a -= b;↵
if(a < 0) a += MOD;↵
}↵
↵
int mmul(int a, int b) {↵
return 1LL * a * b % MOD;↵
}↵
↵
int bpow(int x, int y) {↵
return y == 0 ? 1 : mmul((y % 2) ? x : 1, bpow(mmul(x, x), y / 2));↵
}↵
↵
void tc() {↵
int n; cin >> n >> MOD;↵
vector<int> f(2 * n + 1), invf(2 * n + 1);↵
f[0] = 1;↵
for(int i = 1; i <= 2 * n; i++) {↵
f[i] = mmul(f[i - 1], i);↵
}↵
invf[2 * n] = bpow(f[2 * n], MOD - 2);↵
for(int i = 2 * n; i >= 1; i--) {↵
invf[i - 1] = mmul(invf[i], i);↵
}↵
auto F = [&] (int n, int k) -> int {↵
return mmul(f[n], mmul(invf[k + 1], invf[n - k]));↵
};↵
auto choose = [&] (int n, int k) -> int {↵
return mmul(f[n], mmul(invf[k], invf[n - k]));↵
};↵
vector<vector<int>> p(n + 1, vector<int>(n + 1));↵
for(int i = 0; i <= n; i++) {↵
p[0][i] = mmul(F(2 * i, i), F(2 * i, i));↵
}↵
for(int i = 1; i <= n; i++) {↵
for(int j = 0; j <= n; j++) {↵
for(int k = 0; j + k <= n; k++) {↵
madd(p[i][j + k], mmul(p[i - 1][j], p[0][k]));↵
}↵
}↵
}↵
vector<int> ans(n + 1);↵
for(int i = 0; i <= n; i++) {↵
ans[i] = mmul(F(2 * n, i), p[i][n - i]);↵
}↵
for(int i = n - 1; i >= 0; i--) {↵
for(int j = i + 1; j <= n; j++) {↵
msub(ans[i], mmul(ans[j], choose(j, i)));↵
}↵
}↵
for(int i = 0; i <= n; i++) {↵
cout << ans[i] << " ";↵
}↵
cout << endl;↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t; ↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
[problem:2262F]↵
↵
Authors: [user:sukon,2026-09-12] & [user:kondasujay2,2026-09-12]↵
↵
<spoiler summary="Tutorial">↵
[tutorial:2262F]↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int MXN = 400;↵
↵
template<size_t SZ> int compute_inv(const vector<bitset<SZ>>& mat, vector<bitset<SZ>>& inv) {↵
int n = mat.size();↵
vector<bool> empty(n, true);↵
vector<bitset<SZ>> basis(n);↵
↵
for(int i = 0; i < n; i++) {↵
bitset<SZ> cur = mat[i];↵
bitset<SZ> curinv;↵
curinv[i] = 1;↵
for(int j = 0; j < n; j++) {↵
if(cur[j]) {↵
if(empty[j]) {↵
basis[j] = cur;↵
inv[j] = curinv;↵
empty[j] = false;↵
break;↵
} else {↵
cur ^= basis[j];↵
curinv ^= inv[j];↵
}↵
}↵
}↵
}↵
for(int i = 0; i < n; i++) {↵
if(empty[i]) return 0;↵
}↵
↵
for(int i = n - 1; i >= 1; i--) {↵
for(int j = 0; j < i; j++) {↵
if(basis[j][i]) {↵
basis[j] ^= basis[i];↵
inv[j] ^= inv[i];↵
}↵
}↵
}↵
return 1;↵
}↵
↵
bool try_removal(vector<pair<int, int>> cells, vector<bitset<MXN>>& mat, vector<bitset<MXN>>& inv, vector<int>& row_cnt) {↵
int n = mat.size(), k = cells.size();↵
for(auto [x, y] : cells) {↵
if(mat[x][y] == 0) {↵
return false;↵
}↵
}↵
assert(k < 4);↵
vector<bitset<3>> K(k); ↵
for(int i = 0; i < k; i++) {↵
for(int j = 0; j < k; j++) {↵
K[i][j] = (i == j) ^ inv[cells[i].second][cells[j].first];↵
}↵
}↵
vector<bitset<3>> invK(cells.size());↵
if(!compute_inv(K, invK)) {↵
return false;↵
}↵
for(auto [x, y] : cells) {↵
mat[x][y] = 0;↵
row_cnt[x]--;↵
}↵
↵
auto old = inv;↵
for(int i = 0; i < n; i++) {↵
bitset<3> coef;↵
for(int alpha = 0; alpha < k; alpha++) {↵
int r = cells[alpha].first;↵
↵
if(old[i][r]) {↵
coef ^= invK[alpha];↵
}↵
}↵
↵
// delta = coef * (V^T * old)↵
for(int beta = 0; beta < k; beta++) {↵
if(coef[beta]) {↵
int c = cells[beta].second;↵
inv[i] ^= old[c];↵
}↵
}↵
}↵
return true;↵
}↵
↵
vector<int> compute_matching(const vector<bitset<MXN>>& mat) {↵
int n = mat.size();↵
vector<vector<int>> adj(n);↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < n; j++) {↵
if(mat[i][j]) adj[i].push_back(j);↵
}↵
}↵
↵
vector<int> match(n, -1);↵
vector<bool> done(n);↵
↵
function<bool(int)> dfs = [&] (int s) {↵
for(int u : adj[s]) {↵
if(!done[u]) {↵
done[u] = true;↵
↵
if(match[u] == -1 || dfs(match[u])) {↵
match[u] = s;↵
return true;↵
}↵
}↵
}↵
return false;↵
};↵
↵
for(int i = 0; i < n; i++) {↵
fill(done.begin(), done.end(), false);↵
dfs(i);↵
}↵
↵
for(int i = 0; i < n; i++) {↵
assert(match[i] != -1);↵
}↵
return match;↵
}↵
↵
void tc() {↵
int n, m; cin >> n >> m;↵
↵
vector<bitset<MXN>> mat(n);↵
vector<int> row_cnt(n);↵
for(int i = 0; i < m; i++) {↵
int x, y; cin >> x >> y;↵
x--, y--;↵
mat[x][y] = 1;↵
row_cnt[x]++;↵
}↵
↵
vector<bitset<MXN>> inv(n);↵
compute_inv(mat, inv);↵
↵
int sm = m;↵
int left = (sm + n - 1) / n;↵
cout << left << '\n';↵
↵
while(sm > 0) {↵
vector<bitset<MXN>> omat = mat;↵
if(sm <= n) {↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < n; j++) {↵
mat[i][j] = 0;↵
}↵
}↵
row_cnt.assign(n, 0);↵
} else if(sm <= 2 * n) {↵
vector<int> matching = compute_matching(mat);↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < n; j++) {↵
mat[i][j] = 0;↵
}↵
}↵
row_cnt.assign(n, 0);↵
for(int i = 0; i < sm - n; i++) {↵
mat[matching[i]][i] = 1;↵
row_cnt[matching[i]]++;↵
}↵
} else if(sm <= 3 * n) {↵
vector<int> matching = compute_matching(mat);↵
int above = 0;↵
for(int i = 0; i < n; i++) {↵
for(int j = matching[i] + 1; j < n; j++) {↵
above += mat[j][i];↵
}↵
}↵
↵
vector<bitset<MXN>> nmat(n);↵
vector<int> nrow_cnt(n);↵
int ones_left = sm - n;↵
for(int i = 0; i < n; i++) {↵
nmat[matching[i]][i] = 1;↵
nrow_cnt[matching[i]]++;↵
ones_left--;↵
}↵
// make matrix either upper or lower triangular, whichever one↵
// removes a sufficient number of ones↵
if(above >= ones_left) {↵
for(int i = 0; i < n; i++) {↵
for(int j = matching[i] + 1; j < n; j++) {↵
if(mat[j][i]) {↵
ones_left--;↵
nmat[j][i] = 1;↵
nrow_cnt[j]++;↵
if(ones_left == 0) break;↵
}↵
}↵
if(ones_left == 0) break;↵
}↵
} else {↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < matching[i]; j++) {↵
if(mat[j][i]) {↵
ones_left--;↵
nmat[j][i] = 1;↵
nrow_cnt[j]++;↵
if(ones_left == 0) break;↵
}↵
}↵
if(ones_left == 0) break;↵
}↵
}↵
mat = nmat;↵
row_cnt = nrow_cnt;↵
} else {↵
int csm = sm;↵
if(n % 2) {↵
// odd case (remove either 1 or 3)↵
int dup_row = -1;↵
for(int i = 0; i < n; i++) {↵
if(row_cnt[i] >= 2) {↵
dup_row = i;↵
break;↵
}↵
}↵
assert(dup_row != -1);↵
↵
vector<int> cols;↵
for(int i = 0; i < n; i++) {↵
if(mat[dup_row][i]) cols.push_back(i);↵
}↵
↵
assert(cols.size() >= 2);↵
↵
for(int i = 0; i < n; i++) {↵
if(try_removal({{i, cols[0]}}, mat, inv, row_cnt)) {↵
csm--;↵
break;↵
}↵
if(try_removal({{i, cols[1]}}, mat, inv, row_cnt)) {↵
csm--;↵
break;↵
}↵
}↵
↵
if(csm == sm) {↵
for(int i = 0; i < n; i++) {↵
if(i != dup_row) {↵
// remove L shape↵
if(try_removal(↵
{{i, cols[0]}, ↵
{dup_row, cols[0]}, ↵
{dup_row, cols[1]}},↵
mat, inv, row_cnt)) {↵
csm -= 3;↵
break;↵
}↵
}↵
}↵
assert(sm != csm);↵
}↵
}↵
↵
while(csm > sm - n) {↵
// remove 2 at a time↵
int dup_row = -1;↵
for(int i = 0; i < n; i++) {↵
if(row_cnt[i] >= 3) {↵
dup_row = i;↵
break;↵
}↵
}↵
↵
vector<int> cols;↵
for(int i = 0; i < n; i++) {↵
if(mat[dup_row][i]) cols.push_back(i);↵
}↵
↵
assert(cols.size() >= 3);↵
↵
if(!try_removal({{dup_row, cols[0]}, {dup_row, cols[1]}}, mat, inv, row_cnt)) {↵
if(!try_removal({{dup_row, cols[1]}, {dup_row, cols[2]}}, mat, inv, row_cnt)) {↵
if(!try_removal({{dup_row, cols[0]}, {dup_row, cols[2]}}, mat, inv, row_cnt)) {↵
assert(false);↵
}↵
}↵
}↵
↵
csm -= 2;↵
}↵
assert(csm == sm - n);↵
}↵
↵
vector<pair<int, int>> move;↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < n; j++) {↵
if(omat[i][j] == 1 && mat[i][j] == 0) {↵
move.push_back({i, j});↵
}↵
}↵
}↵
cout << move.size() << "\n";↵
for(auto [x, y] : move) cout << x + 1 << " " << y + 1 << "\n";↵
sm -= n;↵
↵
int csm = 0;↵
for(int i = 0; i < n; i++) {↵
csm += row_cnt[i];↵
}↵
assert(csm == max(0, sm));↵
}↵
}↵
↵
int main() {↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Tester Solution">↵
Will be added later; credit to [user:BurnedChicken,2026-09-10] for finding this in testing!↵
This method results in a much simpler solution!↵
</spoiler>↵
↵
↵
<spoiler>↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int SZ = 400;↵
↵
↵
template<size_t SZ> int compute_inv(const vector<bitset<SZ>>& mat, vector<bitset<SZ>>& inv) {↵
int n = mat.size();↵
vector<bool> empty(n, true);↵
vector<bitset<SZ>> basis(n);↵
↵
for(int i = 0; i < n; i++) {↵
bitset<SZ> cur = mat[i];↵
bitset<SZ> curinv;↵
curinv[i] = 1;↵
for(int j = 0; j < n; j++) {↵
if(cur[j]) {↵
if(empty[j]) {↵
basis[j] = cur;↵
inv[j] = curinv;↵
empty[j] = false;↵
break;↵
} else {↵
cur ^= basis[j];↵
curinv ^= inv[j];↵
}↵
}↵
}↵
}↵
for(int i = 0; i < n; i++) {↵
if(empty[i]) return 0;↵
}↵
↵
for(int i = n - 1; i >= 1; i--) {↵
for(int j = 0; j < i; j++) {↵
if(basis[j][i]) {↵
basis[j] ^= basis[i];↵
inv[j] ^= inv[i];↵
}↵
}↵
}↵
return 1;↵
}↵
↵
void tc() {↵
int n, m; cin >> n >> m;↵
vector<bitset<SZ>> mat(n);↵
for(int i = 0; i < m; i++) {↵
int x, y; cin >> x >> y;↵
x--, y--;↵
mat[x][y] = 1;↵
}↵
↵
vector<bitset<SZ>> inv(n);↵
compute_inv(mat, inv);↵
vector<int> cnts(2 * n);↵
for(int i = 0; i < n; i++) {↵
for(int j = 0; j < n; j++) {↵
cnts[i] += mat[i][j];↵
cnts[n + j] += mat[i][j];↵
}↵
}↵
queue<pair<int, int>> mustq, freeq;↵
vector<pair<int, int>> centers;↵
vector<vector<pair<int, int>>> moves;↵
while(true) {↵
while(mustq.size() + freeq.size() < n) {↵
int best_rc = 0;↵
for(int rc = 0; rc < 2 * n; rc++) {↵
if(cnts[rc] >= cnts[best_rc]) best_rc = rc;↵
}↵
if(cnts[best_rc] == 0) {↵
break;↵
}↵
↵
int x = -1, y = -1;↵
if(best_rc < n) {↵
x = best_rc;↵
for(int j = 0; j < n; j++) {↵
if(mat[x][j] && inv[j][x]) {↵
y = j;↵
break;↵
}↵
}↵
} else {↵
y = best_rc - n;↵
for(int j = 0; j < n; j++) {↵
if(mat[j][y] && inv[y][j]) {↵
x = j;↵
break;↵
}↵
}↵
}↵
assert(x != -1 && y != -1);↵
↵
centers.push_back({x, y});↵
vector<pair<int, int>> must, free;↵
auto erase = [&] (int a, int b) {↵
mat[a][b] = 0;↵
cnts[a]--;↵
cnts[b + n]--;↵
};↵
for(int j = 0; j < n; j++) {↵
if(mat[x][j] && j != y) {↵
must.push_back({x, j});↵
erase(x, j);↵
}↵
}↵
for(int j = 0; j < n; j++) {↵
if(mat[j][y] && j != x) {↵
free.push_back({j, y});↵
erase(j, y);↵
}↵
}↵
erase(x, y);↵
assert(cnts[x] == 0 && cnts[n + y] == 0);↵
↵
if(best_rc < n) swap(must, free);↵
for(auto u : must) mustq.push(u);↵
for(auto u : free) freeq.push(u);↵
↵
bitset<SZ> row = inv[y];↵
for(int j = 0; j < n; j++) {↵
if(cnts[j + n] > 0 && inv[j][x]) {↵
inv[j] ^= row;↵
}↵
}↵
}↵
int left = n;↵
vector<pair<int, int>> move;↵
while(left > 0 && mustq.size() > 0) {↵
left--;↵
move.push_back(mustq.front());↵
mustq.pop();↵
}↵
while(left > 0 && freeq.size() > 0) {↵
left--;↵
move.push_back(freeq.front());↵
freeq.pop();↵
}↵
while(left > 0 && centers.size() > 0) {↵
left--;↵
move.push_back(centers.back());↵
centers.pop_back();↵
}↵
moves.push_back(move);↵
if(centers.size() == 0) break;↵
}↵
cout << moves.size() << "\n";↵
for(auto move : moves) {↵
cout << move.size() << "\n";↵
for(auto [u, v] : move) cout << u + 1 << " " << v + 1 << "\n";↵
}↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false), cin.tie(nullptr);↵
int t; cin >> t;↵
while(t--) tc();↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the problem">↵
↵
- Amazing: [likes:1,option1]↵
- Good: [likes:1,option2]↵
- Ok: [likes:1,option3]↵
- Bad: [likes:1,option4]↵
- Terrible: [likes:1,option5]↵
↵
</spoiler>↵
↵
