Submission #33651579

---

Source Code Expand

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
#include <random>
#include <bitset>
using namespace std;

using ll = long long;
using ull = unsigned long long;

#define LOG(f...) fprintf(stderr, f)
// #define DBG(f...) printf("%3d: ", __LINE__), printf(f)
#define DBG(f...) void()
#define all(cont) begin(cont), end(cont)
#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

template <class T> void read(T &x) {
  char ch; x = 0;
  int f = 1;
  while (isspace(ch = getchar()));
  if (ch == '-') ch = getchar(), f = -1;
  do x = x * 10 + (ch - '0'); while (isdigit(ch = getchar()));
  x *= f;
}
template <class T, class ...A> void read(T &x, A&... args) { read(x); read(args...); }

const int N = 1005;
const int SIZ = 128;
using BS = bitset<SIZ>;

ull a[N], target[N];

mt19937 rng;
int R(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }

vector<int> ans;

void op(int r) {
  ans.push_back(r);
  for (int i = r; i > 1; --i)
    a[i] ^= a[i - 1];
}

ull b[64];
BS rep[64];

void clear() { memset(b, 0, sizeof(b)); memset(rep, 0, sizeof(rep)); }

void ins(ull x, int pos) {
  BS r; r[pos] = true;
  for (int i = 0; i < 60; ++i) {
    if ((~x >> i) & 1) continue;
    if (!b[i]) {
      b[i] = x;
      rep[i] = r;
      break;
    }
    x ^= b[i];
    r ^= rep[i];
  }
}

bool fail;
BS solve(ll x) {
  BS ans = 0; fail = false;
  for (int i = 0; i < 60; ++i) {
    if ((~x >> i) & 1) continue;
    if (!b[i]) { fail = true; break; }
    x ^= b[i]; ans ^= rep[i];
  }
  return ans;
}

int main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  int n;
  read(n);
  for (int i = 1; i <= n; ++i)
    read(a[i]);
  for (int i = 1; i <= n; ++i)
    read(target[i]);
  auto nosolu = [&]() { puts("No"); exit(0); };
  if (a[1] != target[1]) nosolu();
  for (int i = 1; i < n; ++i) {
    ins(a[i], 0);
    solve(target[i + 1] ^ a[i + 1]);
    if (fail) nosolu();
  }
  for (int i = 1; i <= 1300; ++i) {
    int j = R(2, n);
    op(j);
  }
  for (int i = 1; i <= n + 60; ++i)
    op(n);

  clear();
  for (int i = n; i > 1; --i) {
    DBG("work i = %d\n", i);
    BS s;
    while (true) {
      int j, li;
      ull val = a[i] ^ target[i];
      clear();
      for (j = i - 1, li = max(i - SIZ, 0); j > li; --j) {
        ins(a[j], i - j - 1);
        s = solve(val);
        if (!fail) break;
      }
      if (fail) {
        op(i);
        continue;
      }
      if (s[0]) {
        if (s.count() == 1) {
          assert(a[i - 1] == val);
          op(i);
          assert(a[i] == target[i]);
          break;
        }
        int cnt = 0;
        for (int k = j; k < i; ++k) {
          if (s[i - k - 1]) {
            ++cnt;
            if (cnt == 2) {
              op(k);
              break;
            }
          }
        }
        continue;
      }
      op(i);
    }
  }
  for (int i = 1; i <= n; ++i)
    assert(a[i] == target[i]);
  puts("Yes");
  printf("%d\n", (int)ans.size());
  for (int x : ans)
    printf("%d ", x);
  puts("");
  return 0;
}

Submission Info

Judge Result