CF538G Berserk Robot 题解

Description

有一个机器人，第 \(0\) 秒时在 \((0,0)\) 位置。

机器人会循环执行一个长度为 \(l\) 的指令序列，每秒执行一个指令。

指令有 ULDR 四种，分别代表向上/左/下/右移动一格。

你不知道这个指令序列具体是什么，但是你知道 \(n\) 条信息，第 \(i\) 条信息为「第 \(t_i\) 秒时机器人在 \((x_i,y_i)\)」，保证 \(t\) 递增。

你需要构造一个满足这些信息的指令序列，或判断不存在。

\(n \le 2 \times 10^5\)，\(l \le 2 \times 10^6\)，\(t_i,|x_i|,|y_i| \le 10^{18}\)。

Solution

注意到这里每次移动 \(x,y\) 会互相影响，而不是独立的，考虑把原图转 \(45^{\circ}\) 即点 \((x,y)\) 变为 \((x+y,x-y)\)，这样操作就变为 \((1,1),(1,-1),(-1,1),(-1,-1)\)。

这样已经可以做了，但 \(1,-1\) 这类操作不够优美，考虑让 \((x,y)\) 变为 \(\left(\frac{y+x+t}{2},\frac{y-x+t}{2}\right)\)，操作就只有 \((1,1),(1,0),(0,1),(0,0)\)，这样题目就简化很多了。

先考虑 \(x\) 的情况，对于 \(y\) 同理。

不妨设 \(s_i\) 表示前 \(i\) 个指令对 \(x\) 的贡献值，对于一组信息 \((t_i,x_i)\)，\(r_i=t_i\bmod l,k_i=\left\lfloor\frac{t_i}{l}\right\rfloor\)，一定满足 \(x_i=s_{r_i}+k_is_l\)，所以\(s_{r_i}=x_i-k_is_l\)。

考虑按照 \(r_i\) 排序，容易发现按照 \(r\) 把 \([1,l]\) 分成若干块，对于块内的操作可以随便排序，所以 \(0\leq (x_{i+1}-k_{i+1}s_l)-(x_{i}-k_is_l)\leq r_{i+1}-r_{i}\)，这里为了让 \([1,r_1]\) 和 \([r_n+1,l]\) 这两个块也考虑到，可以加入 \(k=0,r=0,x=0\) 和 \(k=-1,r=l,x=0\) 这两组信息。

通过解不等式就可以得到 \(s_l\) 的范围，然后随便取一个 \(s_l\) 的可能取值对于每个块分别考虑就可以构造出答案了。

时间复杂度：\(O(n\log n+l)\)。

Code

#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 2e5 + 5, kMaxL = 2e6 + 5;

int n, l;
bool ans[kMaxL][2];
std::tuple<int, int, int, int> a[kMaxN];

char getch(bool o1, bool o2) {
  if (!o1 && !o2) return 'D';
  else if (!o1 && o2) return 'L';
  else if (o1 && !o2) return 'R';
  else return 'U';
}

int cei(int x, int k) {
  if (k < 0) x = -x, k = -k;
  if (x >= 0) return (x + k - 1) / k;
  else return -((-x) / k);
  // return ceil((long double)x / k);
}

int flr(int x, int k) {
  if (k < 0) x = -x, k = -k;
  if (x >= 0) return x / k;
  else return -((-x + k - 1) / k);
  // return floor((long double)x / k);
}

void dickdreamer() {
  std::cin >> n >> l;
  for (int i = 1; i <= n; ++i) {
    int t, x, y;
    std::cin >> t >> x >> y;
    if ((x + y - t) & 1) return void(std::cout << "NO\n");
    a[i] = {t % l, t / l, (y + x + t) / 2, (y - x + t) / 2};
  }
  a[++n] = {0, 0, 0, 0}, a[++n] = {l, -1, 0, 0};
  std::sort(a + 1, a + 1 + n);
  int L = 0, R = l;
  for (int i = 1; i < n; ++i) {
    int k = std::get<1>(a[i]) - std::get<1>(a[i + 1]);
    int nl = std::get<2>(a[i]) - std::get<2>(a[i + 1]);
    int nr = nl + std::get<0>(a[i + 1]) - std::get<0>(a[i]);
    assert(nl <= nr);
    if (!k && (nl > 0 || nr < 0)) return void(std::cout << "NO\n");
    if (k > 0)
      L = std::max(L, cei(nl, k)), R = std::min(R, flr(nr, k));
    else if (k < 0)
      L = std::max(L, cei(nr, k)), R = std::min(R, flr(nl, k));
  }
  if (L > R) return void(std::cout << "NO\n");
  for (int i = 1; i < n; ++i) {
    int det = (std::get<2>(a[i + 1]) - L * std::get<1>(a[i + 1])) -
              (std::get<2>(a[i]) - L * std::get<1>(a[i]));
    assert(det >= 0);
    int nl = std::get<0>(a[i]) + 1, nr = std::get<0>(a[i]) + det;
    for (int j = nl; j <= nr; ++j) ans[j][0] = 1;
  }
  L = 0, R = l;
  for (int i = 1; i < n; ++i) {
    int k = std::get<1>(a[i]) - std::get<1>(a[i + 1]);
    int nl = std::get<3>(a[i]) - std::get<3>(a[i + 1]);
    int nr = nl + std::get<0>(a[i + 1]) - std::get<0>(a[i]);
    assert(nl <= nr);
    if (!k && (nl > 0 || nr < 0)) return void(std::cout << "NO\n");
    if (k > 0)
      L = std::max(L, cei(nl, k)), R = std::min(R, flr(nr, k));
    else if (k < 0)
      L = std::max(L, cei(nr, k)), R = std::min(R, flr(nl, k));
  }
  if (L > R) return void(std::cout << "NO\n");
  for (int i = 1; i < n; ++i) {
    int det = (std::get<3>(a[i + 1]) - L * std::get<1>(a[i + 1])) -
              (std::get<3>(a[i]) - L * std::get<1>(a[i]));
    assert(det >= 0);
    int nl = std::get<0>(a[i]) + 1, nr = std::get<0>(a[i]) + det;
    for (int j = nl; j <= nr; ++j) ans[j][1] = 1;
  }

  for (int i = 1; i <= l; ++i) std::cout << getch(ans[i][0], ans[i][1]);
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}