Submission #3452355

---

Source Code Expand

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

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef pair<ll, ll> llll;
typedef pair<double, double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a) int((a).size())
#define pb push_back
#define FOR(var, from, to) for (int var = (from); var <= (to); ++var)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define rep1(var, n) for (int var = 1; var <= (n); ++var)
#define repC2(vari, varj, n)               \
  for (int vari = 0; vari < (n)-1; ++vari) \
    for (int varj = vari + 1; varj < (n); ++varj)
#define ALL(c) (c).begin(), (c).end()
#define RALL(c) (c).rbegin(), (c).rend()
#define tr(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define found(s, e) ((s).find(e) != (s).end())
#define mset(arr, val) memset(arr, val, sizeof(arr))
#define mid(x, y) ((x) + ((y) - (x)) / 2)
#define IN(x, a, b) ((a) <= (x) && (x) <= (b))
#define cons make_pair

template <typename T>
void print_ar(vector<T>& a) {
  int n = a.size();
  cout << n << endl;
  for (int i = 0; i < n; ++i) {
    cout << a[i];
    if (i < n - 1) cout << ' ';
  }
  cout << endl;
}

vector<char> g(int c, int d) {
  assert(c % 2 != 0 && d % 2 != 0);

  vector<char> op(31);

  int r = 1 << 30;
  rep(i, 31) {
    if (c > 0) {
      c -= r;
      if (d > 0) {
        op[i] = 'R';
        d -= r;
      } else {
        op[i] = 'U';
        d += r;
      }
    } else {
      c += r;
      if (d > 0) {
        op[i] = 'D';
        d -= r;
      } else {
        op[i] = 'L';
        d += r;
      }
    }
    r >>= 1;
  }

  reverse(ALL(op));
  return op;
}

vector<char> f(int x, int y) {
  assert((x + y) % 2 != 0);
  return g(x + y, x - y);
}

void check(vi& arms, vector<char>& op, int expected_x, int expected_y) {
  int m = arms.size();
  assert(op.size() == m);
  int x = 0, y = 0;
  rep(i, m) {
    int a = arms[i];
    switch (op[i]) {
      case 'R':
        x += a;
        break;
      case 'L':
        x -= a;
        break;
      case 'U':
        y += a;
        break;
      case 'D':
        y -= a;
        break;
    }
  }
  if (x != expected_x) {
     fprintf(stderr, "x=%d, expected=%d\n", x, expected_x);
     assert(x == expected_x);
  }
  if (y != expected_y) {
     fprintf(stderr, "y=%d, expected=%d\n", y, expected_y);
    assert(y == expected_y);
  }
  //   fprintf(stderr, "ok.\n");
}

void even(int N, vi& x, vi& y) {
  vi arms;
  for (int i = 0, a = 1; i < 31; ++i, a <<= 1) arms.pb(a);
  arms.pb(1);

  print_ar(arms);

  rep(i, N) {
    vector<char> op = f(x[i] - 1, y[i]);
    op.pb('R');
    cout << string(ALL(op)) << endl;
#ifdef DEBUG
    check(arms, op, x[i], y[i]);
#endif
  }
}
void odd(int N, vi& x, vi& y) {
  vi arms;
  for (int i = 0, a = 1; i < 31; ++i, a <<= 1) arms.pb(a);

  print_ar(arms);

  rep(i, N) {
    vector<char> op = f(x[i], y[i]);
    cout << string(ALL(op)) << endl;
#ifdef DEBUG
    check(arms, op, x[i], y[i]);
#endif
  }
}

void solve(int N, vi& x, vi& y) {
  vi r(2, 0);
  rep(i, N) { r[abs(x[i] + y[i]) % 2]++; }
  if (r[0] == N) {
    even(N, x, y);
  } else if (r[1] == N) {
    odd(N, x, y);
  } else {
    cout << -1 << endl;
  }
}

int main() {
  int N;
  cin >> N;
  vi x(N), y(N);
  rep(i, N) cin >> x[i] >> y[i];
  solve(N, x, y);
  return 0;
}

Submission Info

Judge Result