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;↵
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:2,option1]↵
- Good: [likes:2,option2]↵
- Ok: [likes:2,option3]↵
- Bad: [likes:2,option4]↵
- Terrible: [likes:2,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:3,option1]↵
- Good: [likes:3,option2]↵
- Ok: [likes:3,option3]↵
- Bad: [likes:3,option4]↵
- Terrible: [likes:3,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:4,option1]↵
- Good: [likes:4,option2]↵
- Ok: [likes:4,option3]↵
- Bad: [likes:4,option4]↵
- Terrible: [likes:4,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:5,option1]↵
- Good: [likes:5,option2]↵
- Ok: [likes:5,option3]↵
- Bad: [likes:5,option4]↵
- Terrible: [likes:5,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:6,option1]↵
- Good: [likes:6,option2]↵
- Ok: [likes:6,option3]↵
- Bad: [likes:6,option4]↵
- Terrible: [likes:6,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:7,option1]↵
- Good: [likes:7,option2]↵
- Ok: [likes:7,option3]↵
- Bad: [likes:7,option4]↵
- Terrible: [likes:7,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:8,option1]↵
- Good: [likes:8,option2]↵
- Ok: [likes:8,option3]↵
- Bad: [likes:8,option4]↵
- Terrible: [likes:8,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="Tutorial 2">↵
Will be added later; credit to [user:BurnedChicken,2026-09-10] for finding this in testing!↵
This method results in a much simplerCredit to [user:BurnedChicken,2026-09-10] for finding this in testing!↵
↵
We will first prove that for any row/column of a rank $n$ matrix, we can zero out everything in that row/column except one, and maintain rank $n$. This is because rank $n$ means the determinant is $1$, so there are exactly an odd number of perfect matchings in total (read Solution 1 for more understanding). Therefore at least $1$ of the ones in the row/column must be in an odd number of perfect matchings (since if they were all even then the total number would be even). This means if we delete all other ones but that one, then we would keep rank $n$.↵
↵
This actually all you need to prove to solve the problem. Note that after we clear out one row except one number, we can clear out that column except that one number (even partially) and the determinant will not change (and the same works when clearing out a column with the leftover row). ↵
↵
For every turn, we want to try to find $n$ things to remove without changing the rank. Therefore, we begin by finding the one in the biggest row/column we can keep while removing everything else. Then we remove everything in the column/row of that one, and the everything in the row/column into the queue. If the queue + the current removals is big enough to reach $n$ removals, then we can just remove the ones in the queue. If the queue is too small, then we repeat one the next biggest row/column. Because the queue contains the row/column with the most ones, when the current removals will never exceed $n$ if the the queue + current removals is less than $n$. Once we run out of row/columns to clear, we can start removing the ones we excluded removing, since we have to reduce the rank at this point.↵
↵
To find the one we must keep, you have to utilize the inverse, since we can clear out the row/column on $M_{i, j}$ if $M^{-1}_{j, i} = 1$ (proof is by Cramer's Rule). We can keep track of the inverse after this clear out operation in $O(n^2 / w)$ if done properly (using something similar to Woodbury Matrix Identity, look at Solution 1 for details). If implemented properly, this results in a $O(n^3 / w)$ solution!.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution 2">↵
↵
~~~~~↵
#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:9,option1]↵
- Good: [likes:9,option2]↵
- Ok: [likes:9,option3]↵
- Bad: [likes:9,option4]↵
- Terrible: [likes:9,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;↵
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:2,option1]↵
- Good: [likes:2,option2]↵
- Ok: [likes:2,option3]↵
- Bad: [likes:2,option4]↵
- Terrible: [likes:2,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:3,option1]↵
- Good: [likes:3,option2]↵
- Ok: [likes:3,option3]↵
- Bad: [likes:3,option4]↵
- Terrible: [likes:3,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:4,option1]↵
- Good: [likes:4,option2]↵
- Ok: [likes:4,option3]↵
- Bad: [likes:4,option4]↵
- Terrible: [likes:4,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:5,option1]↵
- Good: [likes:5,option2]↵
- Ok: [likes:5,option3]↵
- Bad: [likes:5,option4]↵
- Terrible: [likes:5,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:6,option1]↵
- Good: [likes:6,option2]↵
- Ok: [likes:6,option3]↵
- Bad: [likes:6,option4]↵
- Terrible: [likes:6,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:7,option1]↵
- Good: [likes:7,option2]↵
- Ok: [likes:7,option3]↵
- Bad: [likes:7,option4]↵
- Terrible: [likes:7,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:8,option1]↵
- Good: [likes:8,option2]↵
- Ok: [likes:8,option3]↵
- Bad: [likes:8,option4]↵
- Terrible: [likes:8,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="Tutorial 2">↵
This method results in a much simpler
↵
We will first prove that for any row/column of a rank $n$ matrix, we can zero out everything in that row/column except one, and maintain rank $n$. This is because rank $n$ means the determinant is $1$, so there are exactly an odd number of perfect matchings in total (read Solution 1 for more understanding). Therefore at least $1$ of the ones in the row/column must be in an odd number of perfect matchings (since if they were all even then the total number would be even). This means if we delete all other ones but that one, then we would keep rank $n$.↵
↵
This actually all you need to prove to solve the problem. Note that after we clear out one row except one number, we can clear out that column except that one number (even partially) and the determinant will not change (and the same works when clearing out a column with the leftover row). ↵
↵
For every turn, we want to try to find $n$ things to remove without changing the rank. Therefore, we begin by finding the one in the biggest row/column we can keep while removing everything else. Then we remove everything in the column/row of that one, and the everything in the row/column into the queue. If the queue + the current removals is big enough to reach $n$ removals, then we can just remove the ones in the queue. If the queue is too small, then we repeat one the next biggest row/column. Because the queue contains the row/column with the most ones, when the current removals will never exceed $n$ if the the queue + current removals is less than $n$. Once we run out of row/columns to clear, we can start removing the ones we excluded removing, since we have to reduce the rank at this point.↵
↵
To find the one we must keep, you have to utilize the inverse, since we can clear out the row/column on $M_{i, j}$ if $M^{-1}_{j, i} = 1$ (proof is by Cramer's Rule). We can keep track of the inverse after this clear out operation in $O(n^2 / w)$ if done properly (using something similar to Woodbury Matrix Identity, look at Solution 1 for details). If implemented properly, this results in a $O(n^3 / w)$ solution
</spoiler>↵
↵
↵
<spoiler summary="Solution 2">↵
↵
~~~~~↵
#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:9,option1]↵
- Good: [likes:9,option2]↵
- Ok: [likes:9,option3]↵
- Bad: [likes:9,option4]↵
- Terrible: [likes:9,option5]↵
↵
</spoiler>↵
↵
