提出 #70508492

---

ソースコード 拡げる

import std.conv, std.functional, std.range, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.bitmanip, std.complex, std.container, std.math, std.mathspecial, std.numeric, std.regex, std.typecons;
import core.bitop;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; }
int readInt() { return readToken.to!int; }
long readLong() { return readToken.to!long; }

string COLOR(string s = "") { return "\x1b[" ~ s ~ "m"; }

bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } }
bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } }

int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; }
int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); }
int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); }


alias Op = Tuple!(int, "l0", int, "r0", int, "l1", int, "r1");
enum NO = [Op(-1, -1, -1, -1)];

Op[] solve(int N, const(int[]) A, const(int[]) B) {
  int[] xs, ys;
  foreach (i; 0 .. N) if (A[i]) xs ~= i;
  foreach (i; 0 .. N) if (B[i]) ys ~= i;
  if (xs.length != ys.length) return NO;
  if (xs.sum != ys.sum) return NO;
  if (xs.length > N - xs.length) {
    xs = [];
    ys = [];
    foreach (i; 0 .. N) if (!A[i]) xs ~= i;
    foreach (i; 0 .. N) if (!B[i]) ys ~= i;
  }
  debug writeln(xs, " -> ", ys);
  const K = cast(int)(xs.length);
  int[] incs, decs;
  for (int i = 0, j, k; i < K; i = k) {
    for (j = i; j < K && xs[j] <= ys[j]; ++j) {}
    for (k = j; k < K && xs[k] >= ys[k]; ++k) {}
    foreach_reverse (l; i .. j) incs ~= l;
    foreach (l; j .. k) decs ~= l;
  }
  Op[] ops;
  for (int i, j; ; ) {
    for (; i < incs.length && xs[incs[i]] == ys[incs[i]]; ++i) {}
    for (; j < decs.length && xs[decs[j]] == ys[decs[j]]; ++j) {}
    if (i == incs.length || j == decs.length) break;
    const t = min(ys[incs[i]] - xs[incs[i]], xs[decs[j]] - ys[decs[j]]);
    assert(t > 0);
    Op op = Op(xs[incs[i]], xs[incs[i]] + t + 1, xs[decs[j]] - t, xs[decs[j]] + 1);
    if (op.l0 > op.l1) {
      swap(op.l0, op.l1);
      swap(op.r0, op.r1);
    }
    ops ~= op;
    xs[incs[i]] += t;
    xs[decs[j]] -= t;
  }
  assert(xs == ys);
  return ops;
}

void main() {
  try {
    for (; ; ) {
      const numCases = readInt;
      foreach (caseId; 0 .. numCases) {
        const N = readInt;
        auto A = new int[N]; foreach (i; 0 .. N) A[i] = readInt;
        auto B = new int[N]; foreach (i; 0 .. N) B[i] = readInt;
        
        const ans = solve(N, A, B);
        if (ans != NO) {
          writeln("Yes");
          writeln(ans.length);
          foreach (Op op; ans) {
            writeln(op.l0 + 1, " ", op.r0, " ", op.l1 + 1, " ", op.r1);
          }
        } else {
          writeln("No");
        }
      }
    }
  } catch (EOFException e) {
  }
}

提出情報

ジャッジ結果