1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
| #include <cassert> #include <iostream> #include <iterator> #include <numeric> #include <set> #include <utility> #include <vector> #define all(x) (x).begin(), (x).end() using vi = std::vector<int>; using pii = std::pair<int, int>;
int main() { int n; std::cin >> n;
std::vector<int> a(n), b(n); for (auto &x : a) std::cin >> x; for (auto &x : b) std::cin >> x;
if (std::accumulate(all(a), 0) != std::accumulate(all(b), 0)) return std::cout << "No\n", 0;
if (n == 2) { if (a[0] == b[0] && a[1] == b[1]) std::cout << "Yes\n0\n"; else if (a[1] - 1 == b[0] && a[0] + 1 == b[1]) std::cout << "Yes\n1\n1 2\n"; else std::cout << "No\n"; return 0; }
std::vector<pii> answer; auto swap = [&](int i, int j) { assert(0 <= i && i < j && j < n); std::swap(a[i], a[j]); a[i]--, a[j]++; answer.emplace_back(i, j); };
auto prefix_incdec = [&](int z, int x, int y) { assert(0 <= z && z < x && x < y && y < n); swap(x, y), swap(z, y), swap(z, x), swap(z, y); }; auto prefix_decinc = [&](int z, int x, int y) { assert(0 <= z && z < x && x < y && y < n); swap(z, y), swap(z, x), swap(z, y), swap(x, y); }; auto suffix_incdec = [&](int x, int y, int z) { assert(0 <= x && x < y && y < z && z < n); swap(x, y), swap(y, z), swap(x, z), swap(y, z); }; auto suffix_decinc = [&](int x, int y, int z) { assert(0 <= x && x < y && y < z && z < n); swap(y, z), swap(x, z), swap(y, z), swap(x, y); }; auto mid_incdec = [&](int x, int y, int z) { assert(0 <= x && x < y && y < z && z < n); swap(x, y), swap(y, z), swap(x, y), swap(x, z); }; auto mid_decinc = [&](int x, int y, int z) { assert(0 <= x && x < y && y < z && z < n); swap(x, z), swap(y, z), swap(x, y), swap(y, z); }; auto call = [&](int T, auto F, int x, int y, int z) { assert(0 <= x && x < y && y < z && z < n); for (int i = 0; i < T; i++) F(x, y, z); };
for (int i = 0; i < n; i++) { if (a[i] == b[i]) continue;
int j = i + 1, maxv = -1, rec = -1; for (; j < n; j++) if ((a[j] > b[j]) != (a[i] > b[i]) && abs(a[j] - b[j]) > maxv) rec = j, maxv = abs(a[j] - b[j]);
j = rec;
if (a[i] > b[i]) { int dec = a[i] - b[i]; if (i + 1 == j) { if (i == 0) call(dec, suffix_decinc, i, j, n - 1); else call(dec, prefix_decinc, 0, i, j); } else call(dec, mid_decinc, i, j - 1, j); } else { int inc = b[i] - a[i]; if (i + 1 == j) { if (i == 0) call(inc, suffix_incdec, i, j, n - 1); else call(inc, prefix_incdec, 0, i, j); } else call(inc, mid_incdec, i, j - 1, j); } }
if (answer.size() > 31000) std::cout << "No\n"; else { std::cout << "Yes\n" << answer.size() << "\n"; for (auto [i, j] : answer) std::cout << i + 1 << " " << j + 1 << "\n"; } }
|