Submission #66164996

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
constexpr int MAXN = 1'000'007;
constexpr int INF = 2'000'000'000;
constexpr ll INFF = 1'000'000'000'000'000'000LL;
constexpr ll MOD = 998'244'353;
#define mkp make_pair
#define F first
#define S second
#define pb emplace_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()

int32_t main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  for (int i = 0; i < n; i++)
    cin >> b[i];

  if (accumulate(all(a), 0) != accumulate(all(b), 0)) {
    cout << "No\n";
    return 0;
  }
  if (n == 2) {
    if (a[0] == b[0] && a[1] == b[1])
      cout << "Yes\n" << 0 << '\n';
    else if (b[0] == a[1] - 1 && b[1] == a[0] + 1)
      cout << "Yes\n" << 1 << '\n' << 1 << ' ' << 2 << '\n';
    else
      cout << "No\n";
    return 0;
  } else {
    vector<pii> ans;

    auto plus1_1 = [&](int x, int y) {
      ans.pb(x, y);
      ans.pb(y, y + 1);
      ans.pb(x, y + 1);
      ans.pb(y, y + 1);
    };

    auto minus1_1 = [&](int x, int y) {
      ans.pb(x, y + 1);
      ans.pb(y, y + 1);
      ans.pb(x, y + 1);
      ans.pb(x, y);
    };

    auto plus1_2 = [&](int x, int y) {
      ans.pb(x, y);
      ans.pb(x - 1, y);
      ans.pb(x - 1, x);
      ans.pb(x - 1, y);
    };

    auto minus1_2 = [&](int x, int y) {
      ans.pb(x - 1, y);
      ans.pb(x - 1, x);
      ans.pb(x - 1, y);
      ans.pb(x, y);
    };

    while (a[0] != b[0]) {
      if (a[0] > b[0]) {
        minus1_1(1, 2);
        a[0]--, a[1]++;
      } else {
        plus1_1(1, 2);
        a[0]++, a[1]--;
      }
    }
    vector<pii> v;
    for (int i = 1; i < n; i++) {
      int diff = b[i] - a[i];
      if (diff < 0) {
        for (int j = 1; j <= abs(diff); j++) {
          if (!v.empty() && v.back().F == 1) {
            if (i != n - 1)
              plus1_1(v.back().S, i + 1);
            else
              plus1_2(v.back().S, i + 1);
            v.pop_back();
          } else {
            v.pb(-1, i + 1);
          }
        }
      } else if (diff > 0) {
        for (int j = 1; j <= abs(diff); j++) {
          if (!v.empty() && v.back().F == -1) {
            if (i != n - 1)
              minus1_1(v.back().S, i + 1);
            else
              minus1_2(v.back().S, i + 1);
            v.pop_back();
          } else {
            v.pb(1, i + 1);
          }
        }
      }
    }

    cout << "Yes\n";
    cout << sz(ans) << '\n';
    for (auto [x, y] : ans)
      cout << x << ' ' << y << '\n';
  }
}
/*
- How to come up with solutions? (https://hackmd.io/-3cIVAFSQMC3iJTh9EpszA)
  - Play with some small examples.
  - Make observations (or random guesses) by intuition.
    - Try to find counterexamples of the "observations."
  - Find the characteristics of an optimal solution.
  - Try to solve simple cases.
  - Brute force and print out the results.
  - Pick a method (greedy, dp, d&c, ...)
    - But DO NOT force algos on problems!
  - IF YOU'RE STUCK, TRY SOMETHING ELSE! Make new observations!

- Before writing the solution:
  - check TL/ML/correctness of samples/implementation details!

- Pre-submit:
  - Did you make a typo when copying a template?
  - Test more cases if unsure.
    - Write a naive solution and check small cases.
  - Submit the correct file.

- Debugging:
  - General Debugging:
    - Read the whole problem again.
    - Think over the algorithm again.
    - Go to the toilet.

  - Wrong Answer:
    - Any possible overflows?
      - > `__int128` ?
      - Try `-ftrapv` or `#pragma GCC optimize("trapv")`
    - Floating point errors?
      - > `long double` ?
      - turn off math optimizations
      - check for `==`, `>=`, `acos(1.000000001)`, etc.
    - Did you forget to sort or unique?
    - Generate large and worst "corner" cases.
    - Check your `m` / `n`, `i` / `j`,  `x` / `y` and `<` / `>`.
    - Are everything initialized or reset properly?
    - Are you sure about the STL thing you are using?
      - Read cppreference.
    - Print everything and run it on pen and paper.

  - Time Limit Exceeded:
    - Calculate your time complexity again.
    - Does the program actually end?
      - Check for `while(q.size())` etc.
    - Test the largest cases locally.
    - Did you do unnecessary stuff?
      - e.g. pass vectors by value
      - e.g. `memset` for every test case
    - Is your constant factor reasonable?

  - Runtime Error:
    - Check memory usage.
      - Forget to clear or destroy stuff?
      - > `vector::shrink_to_fit()`
    - Stack overflow?
    - Bad pointer / array access?
      - Try `-fsanitize=address`
    - Division by zero? NaN's?
*/

Submission Info

Judge Result