AtCoder Regular Contest 103

Submission #3452355

Source codeソースコード

#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

Task問題 D - Robot Arms
User nameユーザ名 naoya_t
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 600
Source lengthソースコード長 3777 Byte
File nameファイル名
Exec time実行時間 4 ms
Memory usageメモリ使用量 256 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample1.txt,sample2.txt,sample3.txt,sample4.txt
subtask 300 / 300 sample1.txt,sample2.txt,sample3.txt,sample4.txt,sub1.txt,sub10.txt,sub11.txt,sub12.txt,sub13.txt,sub14.txt,sub15.txt,sub16.txt,sub2.txt,sub3.txt,sub4.txt,sub5.txt,sub6.txt,sub7.txt,sub8.txt,sub9.txt
All 300 / 300 sample1.txt,sample2.txt,sample3.txt,sample4.txt,1.txt,10.txt,11.txt,12.txt,13.txt,14.txt,15.txt,16.txt,17.txt,18.txt,19.txt,2.txt,20.txt,21.txt,22.txt,23.txt,24.txt,25.txt,26.txt,27.txt,28.txt,29.txt,3.txt,30.txt,31.txt,32.txt,33.txt,34.txt,4.txt,5.txt,6.txt,7.txt,8.txt,9.txt,sample1.txt,sample2.txt,sample3.txt,sample4.txt,sub1.txt,sub10.txt,sub11.txt,sub12.txt,sub13.txt,sub14.txt,sub15.txt,sub16.txt,sub2.txt,sub3.txt,sub4.txt,sub5.txt,sub6.txt,sub7.txt,sub8.txt,sub9.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
1.txt AC 1 ms 256 KB
10.txt AC 2 ms 256 KB
11.txt AC 4 ms 256 KB
12.txt AC 2 ms 256 KB
13.txt AC 4 ms 256 KB
14.txt AC 4 ms 256 KB
15.txt AC 4 ms 256 KB
16.txt AC 4 ms 256 KB
17.txt AC 2 ms 256 KB
18.txt AC 4 ms 256 KB
19.txt AC 4 ms 256 KB
2.txt AC 1 ms 256 KB
20.txt AC 4 ms 256 KB
21.txt AC 2 ms 256 KB
22.txt AC 2 ms 256 KB
23.txt AC 4 ms 256 KB
24.txt AC 4 ms 256 KB
25.txt AC 4 ms 256 KB
26.txt AC 4 ms 256 KB
27.txt AC 2 ms 256 KB
28.txt AC 4 ms 256 KB
29.txt AC 4 ms 256 KB
3.txt AC 4 ms 256 KB
30.txt AC 4 ms 256 KB
31.txt AC 4 ms 256 KB
32.txt AC 4 ms 256 KB
33.txt AC 4 ms 256 KB
34.txt AC 4 ms 256 KB
4.txt AC 4 ms 256 KB
5.txt AC 4 ms 256 KB
6.txt AC 4 ms 256 KB
7.txt AC 2 ms 256 KB
8.txt AC 4 ms 256 KB
9.txt AC 4 ms 256 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB
sample3.txt AC 1 ms 256 KB
sample4.txt AC 1 ms 256 KB
sub1.txt AC 1 ms 256 KB
sub10.txt AC 1 ms 256 KB
sub11.txt AC 3 ms 256 KB
sub12.txt AC 1 ms 256 KB
sub13.txt AC 3 ms 256 KB
sub14.txt AC 3 ms 256 KB
sub15.txt AC 3 ms 256 KB
sub16.txt AC 3 ms 256 KB
sub2.txt AC 1 ms 256 KB
sub3.txt AC 3 ms 256 KB
sub4.txt AC 3 ms 256 KB
sub5.txt AC 3 ms 256 KB
sub6.txt AC 3 ms 256 KB
sub7.txt AC 1 ms 256 KB
sub8.txt AC 3 ms 256 KB
sub9.txt AC 3 ms 256 KB