提出 #35616036

---

ソースコード 拡げる

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

const int limit = 2000000;
const int maxN = 300011;
const int base = 2000000;

struct Crazy {
  int l, r; 
  vector<int> data;
  bool rev;

  Crazy() {}

  Crazy(int low, int high) {
    l = 0; 
    r = high - low;
    rev = false;
    data.resize(limit);

    for (int i = low; i <= high; i++)
      data[i - low] = i + base;
  }

  int& operator[](int id) {
    if (!rev)
      return data[(l + id) % limit];
    else
      return data[(r - id + limit) % limit];
  }

  void extend_raw(int extra) {
    if (!rev)
      l = (l - extra + limit) % limit;
    else
      r = (r + extra) % limit;
  }

  void revert() {
    rev = !rev;
  }

  void extend(int extra, int step) {
    Crazy& me = *this;

    extend_raw(extra + 1);
    me[extra] = -step;
    for (int i = 1; i <= extra; i++) {
      me[extra - i] = me[extra + i];
      if (me[extra - i] > 0)
        me[extra - i] = 2 * base - me[extra - i];
    }
  }
};

int n, m;
int x[maxN];
int d[maxN];
Crazy crazy;

void solve(int step, int l, int r) {
  if (l > r) {
    crazy = Crazy(1, 0);
    return;
  }

  if (step == m + 1) {
    crazy = Crazy(l, r);
    return;
  }
  const int dd = d[step];
  l -= dd; r -= dd;

  if (l > 0) {
    solve(step + 1, l, r);
  } else if (r < 0) {
    solve(step + 1, -r, -l);
    crazy.revert();
  } else if (-l <= r) {
    solve(step + 1, 1, r);
    crazy.extend(-l, step);
  } else {
    solve(step + 1, 1, -l);
    crazy.extend(r, step);
    crazy.revert();
  }
}

int main()
{
  cin >> n >> m;

  for (int i = 1; i <= n; i++)
    cin >> x[i];

  for (int i = 1; i <= m; i++)
    cin >> d[i];

  solve(1, 1, 1000000);
  
  for (int i = 1; i <= n; i++) {
    int val = crazy[x[i] - 1];

    if (val < 0)
      cout << "Yes " << -val << '\n';
    else
      cout << "No " << (crazy.rev ? base - val : val - base) << '\n';
  }


  return 0;
}

提出情報

ジャッジ結果