Thank you for participating! We hope you enjoyed our problems↵
↵
Author and developer is [user:yunetive29,2025-02-02]↵
[problem:2059A]↵
------------------↵
↵
<spoiler summary="Solution">↵
[tutorial:2059A]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int a[55],b[55];↵
↵
void solve(){↵
int n;cin>>n;↵
set<int> sa,sb;↵
for(int i=1;i<=n;i++)cin>>a[i],sa.insert(a[i]);↵
for(int i=1;i<=n;i++)cin>>b[i],sb.insert(b[i]);↵
if(sa.size()+sb.size()<4){↵
cout<<"NO\n";↵
}else{↵
cout<<"YES\n";↵
}↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int t;cin>>t;↵
while(t--){↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2059B]↵
------------------↵
Author and developer is [user:yunetive29,2025-02-02]↵
↵
<spoiler summary="Solution">↵
[tutorial:2059B]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n, k;↵
cin >> n >> k;↵
k /= 2;↵
vector<int> a(n);↵
for (auto &it: a) cin >> it;↵
if (2 * k == n) {↵
for (int i = 1; i < n; i += 2) {↵
if (a[i] != (i + 1) / 2) {↵
cout << (i + 1) / 2 << '\n';↵
return;↵
}↵
}↵
cout << k + 1 << '\n';↵
} else {↵
for (int i = 1; i <= n - 2 * k + 1; i++) {↵
if (a[i] != 1) {↵
cout << "1\n";↵
return;↵
}↵
}↵
cout << "2\n";↵
}↵
}↵
↵
int main() {↵
int T = 1;↵
cin >> T;↵
while (T--) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2059C]↵
------------------↵
Author and developer is [user:yunetive29,2025-02-02]↵
↵
<spoiler summary="Solution">↵
[tutorial:2059C]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N=305;↵
↵
int a[N][N],suff[N];↵
↵
void solve(){↵
int n;cin>>n;↵
for(int i=1;i<=n;i++){↵
suff[i]=0;↵
for(int j=1;j<=n;j++){↵
cin>>a[i][j];↵
}↵
}↵
for(int i=1;i<=n;i++){↵
for(int j=n;j>=1;j--){↵
if(a[i][j]!=1)break;↵
suff[i]++;↵
}↵
}↵
multiset<int> s;↵
for(int i=1;i<=n;i++){↵
s.insert(suff[i]);↵
}↵
int ans=1;↵
while(!s.empty()){↵
int cur=*s.begin();↵
if(cur>=ans){↵
ans++;↵
}↵
s.extract(cur);↵
}↵
cout<<min(ans,n)<<'\n';↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int t;cin>>t;↵
while(t--){↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[problem:2059D]↵
------------------↵
Author and developer is [user:yunetive29,2025-02-02]↵
↵
<spoiler summary="Solution">↵
[tutorial:2059D]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
#define int long long↵
#define eb emplace_back↵
↵
const int INF = 1e18;↵
↵
void solve() {↵
int n, s1, s2;↵
cin >> n >> s1 >> s2;↵
s1--, s2--;↵
vector<vector<int>> g1(n), g2(n);↵
vector<bool> good(n);↵
set<pair<int, int>> edges;↵
int m1;↵
cin >> m1;↵
for (int i = 0; i < m1; i++) {↵
int v, u;↵
cin >> v >> u;↵
v--, u--;↵
if (v > u)↵
swap(v, u);↵
edges.insert({v, u});↵
g1[v].eb(u);↵
g1[u].eb(v);↵
}↵
int m2;↵
cin >> m2;↵
for (int i = 0; i < m2; i++) {↵
int v, u;↵
cin >> v >> u;↵
v--, u--;↵
if (v > u)↵
swap(v, u);↵
if (edges.find({v, u}) != edges.end())↵
good[v] = true, good[u] = true;↵
g2[v].eb(u);↵
g2[u].eb(v);↵
}↵
vector<vector<int>> d(n, vector<int> (n, INF));↵
d[s1][s2] = 0;↵
set<pair<int, pair<int, int>>> st;↵
st.insert({0, {s1, s2}});↵
while (!st.empty()) {↵
auto [v, u] = st.begin()->second;↵
st.erase(st.begin());↵
for (auto to1 : g1[v]) {↵
for (auto to2 : g2[u]) {↵
int w = abs(to1 - to2);↵
if (d[to1][to2] > d[v][u] + w) {↵
st.erase({d[to1][to2], {to1, to2}});↵
d[to1][to2] = d[v][u] + w;↵
st.insert({d[to1][to2], {to1, to2}});↵
}↵
}↵
}↵
}↵
int ans = INF;↵
for (int i = 0; i < n; i++) {↵
if (!good[i])↵
continue;↵
ans = min(ans, d[i][i]);↵
}↵
if (ans == INF)↵
ans = -1;↵
cout << ans << '\n';↵
}↵
↵
signed main() {↵
//cout << fixed << setprecision(5);↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int T = 1;↵
cin >> T;↵
//cin >> G;↵
while (T--)↵
solve();↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
[problem:2059E1]↵
------------------↵
Author [user:shfs,2025-02-02] and developer is [user:yunetive29,2025-02-02]↵
↵
<spoiler summary="Hint 1">↵
To minimize the number of operations, it is necessary to leave as many elements as possible in the original array. What are these elements?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
These elements must form the initial array prefix and the final array subsequence.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
What other condition needs to be imposed on the prefix so that additions can be used to obtain the final array?↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
[tutorial:2059E1]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
void solve() {↵
int n, m;↵
cin >> n >> m;↵
vector<int> a(n * m + 1), b(n * m + 1);↵
vector<deque<int>> mat(n + 1, deque<int> (m));↵
for (int i = 1; i <= n; i++) {↵
for (int j = 0; j < m; j++) {↵
int ind = j + 1 + (i - 1) * m;↵
mat[i][j] = ind;↵
cin >> a[ind];↵
}↵
}↵
for (int i = 1; i <= n * m; i++)↵
cin >> b[i];↵
map<int, int> mp;↵
for (int i = 1; i <= n * m; i++)↵
mp[b[i]] = i;↵
vector<int> s(n * m + 1), pos(n * m + 1, -1);↵
for (int i = 1; i <= n * m; i++) {↵
if (mp.find(a[i]) != mp.end())↵
pos[i] = mp[a[i]];↵
else↵
break;↵
}↵
pos[0] = 0;↵
int skipped = 0, pref = 0;↵
bool prev = true;↵
for (int i = 1; i <= n * m; i++) {↵
if (pos[i - 1] > pos[i])↵
break;↵
int d = pos[i] - pos[i - 1] - 1;↵
if (prev)↵
skipped += d;↵
else if (d > 0)↵
break;↵
if (skipped >= m - 1)↵
prev = true;↵
else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0)↵
prev = true;↵
else↵
prev = false;↵
if (prev)↵
pref = i;↵
}↵
cout << n * m - pref << '\n';↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int T = 1;↵
cin >> T;↵
while (T--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2059E2]↵
------------------↵
Author [user:shfs,2025-02-02] and developer is [user:yunetive29,2025-02-02]↵
↵
<spoiler summary="Solution">↵
[tutorial:2059E2]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define eb emplace_back↵
#define int long long↵
#define all(x) x.begin(), x.end()↵
#define fi first↵
#define se second↵
↵
const int INF = 1e9 + 1000;↵
↵
struct segtree {↵
vector<pair<int, int>> tree;↵
vector<int> ass;↵
int size = 1;↵
↵
void init(vector<int> &a) {↵
while (a.size() >= size) {↵
size <<= 1;↵
}↵
tree.assign(2 * size, {});↵
ass.assign(2 * size, 0);↵
build(0, 0, size, a);↵
}↵
↵
void build(int x, int lx, int rx, vector<int> &a) {↵
if (rx - lx == 1) {↵
tree[x].se = lx;↵
if (lx < a.size()) {↵
tree[x].fi = a[lx];↵
} else {↵
tree[x].fi = INF;↵
}↵
return;↵
}↵
int m = (lx + rx) / 2;↵
build(2 * x + 1, lx, m, a);↵
build(2 * x + 2, m, rx, a);↵
tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);↵
}↵
↵
void push(int x, int lx, int rx) {↵
tree[x].fi += ass[x];↵
if (rx - lx == 1) {↵
ass[x] = 0;↵
return;↵
}↵
ass[2 * x + 1] += ass[x];↵
ass[2 * x + 2] += ass[x];↵
ass[x] = 0;↵
}↵
↵
void update(int l, int r, int val, int x, int lx, int rx) {↵
push(x, lx, rx);↵
if (l <= lx && rx <= r) {↵
ass[x] += val;↵
push(x, lx, rx);↵
return;↵
}↵
if (rx <= l || r <= lx) {↵
return;↵
}↵
int m = (lx + rx) / 2;↵
update(l, r, val, 2 * x + 1, lx, m);↵
update(l, r, val, 2 * x + 2, m, rx);↵
tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);↵
}↵
↵
void update(int l, int r, int val) {↵
update(l, r + 1, val, 0, 0, size);↵
}↵
↵
int req(int x, int lx, int rx) {↵
push(x, lx, rx);↵
if (rx - lx == 1) {↵
return tree[x].se;↵
}↵
int m = (lx + rx) / 2;↵
push(2 * x + 1, lx, m);↵
push(2 * x + 2, m, rx);↵
if (tree[2 * x + 2].fi == 0) {↵
return req(2 * x + 2, m, rx);↵
} else {↵
return req(2 * x + 1, lx, m);↵
}↵
}↵
↵
int req() {↵
return req(0, 0, size);↵
}↵
};↵
↵
void solve() {↵
int n, m;↵
cin >> n >> m;↵
vector<int> a(n * m + 1), b(n * m + 1);↵
for (int i = 1; i <= n; i++) {↵
for (int j = 0; j < m; j++) {↵
int ind = j + 1 + (i - 1) * m;↵
cin >> a[ind];↵
}↵
}↵
for (int i = 1; i <= n * m; i++)↵
cin >> b[i];↵
map<int, int> mp;↵
for (int i = 1; i <= n * m; i++)↵
mp[b[i]] = i;↵
vector<int> s(n * m + 1), pos(n * m + 1, -1);↵
for (int i = 1; i <= n * m; i++) {↵
if (mp.find(a[i]) != mp.end())↵
pos[i] = mp[a[i]];↵
else↵
break;↵
}↵
pos[0] = 0;↵
int skipped = 0, pref = 0;↵
bool prev = true;↵
for (int i = 1; i <= n * m; i++) {↵
if (pos[i - 1] > pos[i])↵
break;↵
int d = pos[i] - pos[i - 1] - 1;↵
if (prev)↵
skipped += d;↵
else if (d > 0)↵
break;↵
if (skipped >= m - 1)↵
prev = true;↵
else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0)↵
prev = true;↵
else↵
prev = false;↵
if (prev)↵
pref = i;↵
}↵
for (int i = 1; i <= pref; i++) {↵
s[i - 1] = pos[i] - pos[i - 1] - 1;↵
}↵
s[pref] = n * m - pos[pref];↵
↵
vector<pair<int, int>> ans;↵
↵
int res = 0;↵
for (int i = 0; i <= n * m; i++) {↵
res += s[i];↵
}↵
vector<int> ost(pref + 1);↵
for (int i = 1; i <= pref; i++) {↵
ost[i] = (m - i % m) % m;↵
}↵
for (int i = 0; i <= pref; i++) {↵
if (s[i] == 0) {↵
ost[i] = INF;↵
}↵
}↵
vector<int> gol(pref + 1);↵
gol[0] = 1;↵
for (int i = 1; i <= pref; i++) {↵
gol[i] = (i + m - 1) / m + 1;↵
}↵
↵
segtree tree;↵
↵
tree.init(ost);↵
↵
for (int step = 0; step < res; step++) {↵
int chel = tree.req();↵
ans.eb(gol[chel], b[pos[chel] + s[chel]]);↵
tree.update(chel + 1, pref, -1);↵
s[chel]--;↵
if (s[chel] == 0) {↵
tree.update(chel, chel, INF);↵
}↵
}↵
↵
cout << ans.size() << '\n';↵
for (auto [i, col] : ans) {↵
cout << i << " " << col << '\n';↵
}↵
}↵
↵
signed main() {↵
//cout << fixed << setprecision(5);↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int T = 1;↵
cin >> T;↵
//cin >> G;↵
while (T--)↵
solve();↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
↵
Author and developer is [user:yunetive29,2025-02-02]↵
[problem:2059A]↵
------------------↵
↵
<spoiler summary="Solution">↵
[tutorial:2059A]↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int a[55],b[55];↵
↵
void solve(){↵
int n;cin>>n;↵
set<int> sa,sb;↵
for(int i=1;i<=n;i++)cin>>a[i],sa.insert(a[i]);↵
for(int i=1;i<=n;i++)cin>>b[i],sb.insert(b[i]);↵
if(sa.size()+sb.size()<4){↵
cout<<"NO\n";↵
}else{↵
cout<<"YES\n";↵
}↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int t;cin>>t;↵
while(t--){↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2059B]↵
------------------↵
Author and developer is [user:yunetive29,2025-02-02]↵
↵
<spoiler summary="Solution">↵
[tutorial:2059B]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n, k;↵
cin >> n >> k;↵
k /= 2;↵
vector<int> a(n);↵
for (auto &it: a) cin >> it;↵
if (2 * k == n) {↵
for (int i = 1; i < n; i += 2) {↵
if (a[i] != (i + 1) / 2) {↵
cout << (i + 1) / 2 << '\n';↵
return;↵
}↵
}↵
cout << k + 1 << '\n';↵
} else {↵
for (int i = 1; i <= n - 2 * k + 1; i++) {↵
if (a[i] != 1) {↵
cout << "1\n";↵
return;↵
}↵
}↵
cout << "2\n";↵
}↵
}↵
↵
int main() {↵
int T = 1;↵
cin >> T;↵
while (T--) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2059C]↵
------------------↵
Author and developer is [user:yunetive29,2025-02-02]↵
↵
<spoiler summary="Solution">↵
[tutorial:2059C]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N=305;↵
↵
int a[N][N],suff[N];↵
↵
void solve(){↵
int n;cin>>n;↵
for(int i=1;i<=n;i++){↵
suff[i]=0;↵
for(int j=1;j<=n;j++){↵
cin>>a[i][j];↵
}↵
}↵
for(int i=1;i<=n;i++){↵
for(int j=n;j>=1;j--){↵
if(a[i][j]!=1)break;↵
suff[i]++;↵
}↵
}↵
multiset<int> s;↵
for(int i=1;i<=n;i++){↵
s.insert(suff[i]);↵
}↵
int ans=1;↵
while(!s.empty()){↵
int cur=*s.begin();↵
if(cur>=ans){↵
ans++;↵
}↵
s.extract(cur);↵
}↵
cout<<min(ans,n)<<'\n';↵
}↵
↵
int main(){↵
ios_base::sync_with_stdio(0);↵
cin.tie(0);↵
↵
int t;cin>>t;↵
while(t--){↵
solve();↵
}↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[problem:2059D]↵
------------------↵
Author and developer is [user:yunetive29,2025-02-02]↵
↵
<spoiler summary="Solution">↵
[tutorial:2059D]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
#define int long long↵
#define eb emplace_back↵
↵
const int INF = 1e18;↵
↵
void solve() {↵
int n, s1, s2;↵
cin >> n >> s1 >> s2;↵
s1--, s2--;↵
vector<vector<int>> g1(n), g2(n);↵
vector<bool> good(n);↵
set<pair<int, int>> edges;↵
int m1;↵
cin >> m1;↵
for (int i = 0; i < m1; i++) {↵
int v, u;↵
cin >> v >> u;↵
v--, u--;↵
if (v > u)↵
swap(v, u);↵
edges.insert({v, u});↵
g1[v].eb(u);↵
g1[u].eb(v);↵
}↵
int m2;↵
cin >> m2;↵
for (int i = 0; i < m2; i++) {↵
int v, u;↵
cin >> v >> u;↵
v--, u--;↵
if (v > u)↵
swap(v, u);↵
if (edges.find({v, u}) != edges.end())↵
good[v] = true, good[u] = true;↵
g2[v].eb(u);↵
g2[u].eb(v);↵
}↵
vector<vector<int>> d(n, vector<int> (n, INF));↵
d[s1][s2] = 0;↵
set<pair<int, pair<int, int>>> st;↵
st.insert({0, {s1, s2}});↵
while (!st.empty()) {↵
auto [v, u] = st.begin()->second;↵
st.erase(st.begin());↵
for (auto to1 : g1[v]) {↵
for (auto to2 : g2[u]) {↵
int w = abs(to1 - to2);↵
if (d[to1][to2] > d[v][u] + w) {↵
st.erase({d[to1][to2], {to1, to2}});↵
d[to1][to2] = d[v][u] + w;↵
st.insert({d[to1][to2], {to1, to2}});↵
}↵
}↵
}↵
}↵
int ans = INF;↵
for (int i = 0; i < n; i++) {↵
if (!good[i])↵
continue;↵
ans = min(ans, d[i][i]);↵
}↵
if (ans == INF)↵
ans = -1;↵
cout << ans << '\n';↵
}↵
↵
signed main() {↵
//cout << fixed << setprecision(5);↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int T = 1;↵
cin >> T;↵
//cin >> G;↵
while (T--)↵
solve();↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
[problem:2059E1]↵
------------------↵
Author [user:shfs,2025-02-02] and developer is [user:yunetive29,2025-02-02]↵
↵
<spoiler summary="Hint 1">↵
To minimize the number of operations, it is necessary to leave as many elements as possible in the original array. What are these elements?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
These elements must form the initial array prefix and the final array subsequence.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
What other condition needs to be imposed on the prefix so that additions can be used to obtain the final array?↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
[tutorial:2059E1]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include "bits/stdc++.h"↵
using namespace std;↵
↵
void solve() {↵
int n, m;↵
cin >> n >> m;↵
vector<int> a(n * m + 1), b(n * m + 1);↵
vector<deque<int>> mat(n + 1, deque<int> (m));↵
for (int i = 1; i <= n; i++) {↵
for (int j = 0; j < m; j++) {↵
int ind = j + 1 + (i - 1) * m;↵
mat[i][j] = ind;↵
cin >> a[ind];↵
}↵
}↵
for (int i = 1; i <= n * m; i++)↵
cin >> b[i];↵
map<int, int> mp;↵
for (int i = 1; i <= n * m; i++)↵
mp[b[i]] = i;↵
vector<int> s(n * m + 1), pos(n * m + 1, -1);↵
for (int i = 1; i <= n * m; i++) {↵
if (mp.find(a[i]) != mp.end())↵
pos[i] = mp[a[i]];↵
else↵
break;↵
}↵
pos[0] = 0;↵
int skipped = 0, pref = 0;↵
bool prev = true;↵
for (int i = 1; i <= n * m; i++) {↵
if (pos[i - 1] > pos[i])↵
break;↵
int d = pos[i] - pos[i - 1] - 1;↵
if (prev)↵
skipped += d;↵
else if (d > 0)↵
break;↵
if (skipped >= m - 1)↵
prev = true;↵
else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0)↵
prev = true;↵
else↵
prev = false;↵
if (prev)↵
pref = i;↵
}↵
cout << n * m - pref << '\n';↵
}↵
↵
signed main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int T = 1;↵
cin >> T;↵
while (T--)↵
solve();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[problem:2059E2]↵
------------------↵
Author [user:shfs,2025-02-02] and developer is [user:yunetive29,2025-02-02]↵
↵
<spoiler summary="Solution">↵
[tutorial:2059E2]↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define eb emplace_back↵
#define int long long↵
#define all(x) x.begin(), x.end()↵
#define fi first↵
#define se second↵
↵
const int INF = 1e9 + 1000;↵
↵
struct segtree {↵
vector<pair<int, int>> tree;↵
vector<int> ass;↵
int size = 1;↵
↵
void init(vector<int> &a) {↵
while (a.size() >= size) {↵
size <<= 1;↵
}↵
tree.assign(2 * size, {});↵
ass.assign(2 * size, 0);↵
build(0, 0, size, a);↵
}↵
↵
void build(int x, int lx, int rx, vector<int> &a) {↵
if (rx - lx == 1) {↵
tree[x].se = lx;↵
if (lx < a.size()) {↵
tree[x].fi = a[lx];↵
} else {↵
tree[x].fi = INF;↵
}↵
return;↵
}↵
int m = (lx + rx) / 2;↵
build(2 * x + 1, lx, m, a);↵
build(2 * x + 2, m, rx, a);↵
tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);↵
}↵
↵
void push(int x, int lx, int rx) {↵
tree[x].fi += ass[x];↵
if (rx - lx == 1) {↵
ass[x] = 0;↵
return;↵
}↵
ass[2 * x + 1] += ass[x];↵
ass[2 * x + 2] += ass[x];↵
ass[x] = 0;↵
}↵
↵
void update(int l, int r, int val, int x, int lx, int rx) {↵
push(x, lx, rx);↵
if (l <= lx && rx <= r) {↵
ass[x] += val;↵
push(x, lx, rx);↵
return;↵
}↵
if (rx <= l || r <= lx) {↵
return;↵
}↵
int m = (lx + rx) / 2;↵
update(l, r, val, 2 * x + 1, lx, m);↵
update(l, r, val, 2 * x + 2, m, rx);↵
tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]);↵
}↵
↵
void update(int l, int r, int val) {↵
update(l, r + 1, val, 0, 0, size);↵
}↵
↵
int req(int x, int lx, int rx) {↵
push(x, lx, rx);↵
if (rx - lx == 1) {↵
return tree[x].se;↵
}↵
int m = (lx + rx) / 2;↵
push(2 * x + 1, lx, m);↵
push(2 * x + 2, m, rx);↵
if (tree[2 * x + 2].fi == 0) {↵
return req(2 * x + 2, m, rx);↵
} else {↵
return req(2 * x + 1, lx, m);↵
}↵
}↵
↵
int req() {↵
return req(0, 0, size);↵
}↵
};↵
↵
void solve() {↵
int n, m;↵
cin >> n >> m;↵
vector<int> a(n * m + 1), b(n * m + 1);↵
for (int i = 1; i <= n; i++) {↵
for (int j = 0; j < m; j++) {↵
int ind = j + 1 + (i - 1) * m;↵
cin >> a[ind];↵
}↵
}↵
for (int i = 1; i <= n * m; i++)↵
cin >> b[i];↵
map<int, int> mp;↵
for (int i = 1; i <= n * m; i++)↵
mp[b[i]] = i;↵
vector<int> s(n * m + 1), pos(n * m + 1, -1);↵
for (int i = 1; i <= n * m; i++) {↵
if (mp.find(a[i]) != mp.end())↵
pos[i] = mp[a[i]];↵
else↵
break;↵
}↵
pos[0] = 0;↵
int skipped = 0, pref = 0;↵
bool prev = true;↵
for (int i = 1; i <= n * m; i++) {↵
if (pos[i - 1] > pos[i])↵
break;↵
int d = pos[i] - pos[i - 1] - 1;↵
if (prev)↵
skipped += d;↵
else if (d > 0)↵
break;↵
if (skipped >= m - 1)↵
prev = true;↵
else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0)↵
prev = true;↵
else↵
prev = false;↵
if (prev)↵
pref = i;↵
}↵
for (int i = 1; i <= pref; i++) {↵
s[i - 1] = pos[i] - pos[i - 1] - 1;↵
}↵
s[pref] = n * m - pos[pref];↵
↵
vector<pair<int, int>> ans;↵
↵
int res = 0;↵
for (int i = 0; i <= n * m; i++) {↵
res += s[i];↵
}↵
vector<int> ost(pref + 1);↵
for (int i = 1; i <= pref; i++) {↵
ost[i] = (m - i % m) % m;↵
}↵
for (int i = 0; i <= pref; i++) {↵
if (s[i] == 0) {↵
ost[i] = INF;↵
}↵
}↵
vector<int> gol(pref + 1);↵
gol[0] = 1;↵
for (int i = 1; i <= pref; i++) {↵
gol[i] = (i + m - 1) / m + 1;↵
}↵
↵
segtree tree;↵
↵
tree.init(ost);↵
↵
for (int step = 0; step < res; step++) {↵
int chel = tree.req();↵
ans.eb(gol[chel], b[pos[chel] + s[chel]]);↵
tree.update(chel + 1, pref, -1);↵
s[chel]--;↵
if (s[chel] == 0) {↵
tree.update(chel, chel, INF);↵
}↵
}↵
↵
cout << ans.size() << '\n';↵
for (auto [i, col] : ans) {↵
cout << i << " " << col << '\n';↵
}↵
}↵
↵
signed main() {↵
//cout << fixed << setprecision(5);↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
int T = 1;↵
cin >> T;↵
//cin >> G;↵
while (T--)↵
solve();↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
