Submission #1130098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130098		study__algo	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1097 ms	64224 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

constexpr int N = int(3E4);
constexpr int inf = int(1E9);

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m;
  cin >> n >> m;

  vector<int> b(m);
  vector<int> p(m);
  for (int i = 0; i < m; ++i) {
    cin >> b[i] >> p[i];
  }

  vector<vector<int>> by_p(N + 1);
  for (int i = 0; i < m; ++i) {
    by_p[p[i]].push_back(b[i] % p[i]);
  }

  for (auto& v : by_p) {
    sort(v.begin(), v.end());
    v.resize(distance(v.begin(), unique(v.begin(), v.end())));
  }

  vector<vector<int>> states(n);
  for (int i = 1; i < N; ++i) {
    if (by_p[i].empty()) {
      continue;
    }

    for (int bias = 0; bias + by_p[i][0] < n; bias += i) {
      for (int x : by_p[i]) {
        if (bias + x >= n) {
          break;
        }
        states[bias + x].push_back(i);
      }
    }
  }

  auto getId = [&states](int b, int p) {
    return int(distance(states[b].begin(), lower_bound(states[b].begin(), states[b].end(), p)));
  };

  vector<vector<int>> can_get(n);
  for (int i = 0; i < m; ++i) {
    const int id = getId(b[i], p[i]);
    can_get[b[i]].push_back(id);
  }

  vector<bool> first(n, true);
  vector<vector<int>> d(n);
  for (int i = 0; i < n; ++i) {
    d[i].resize(states[i].size(), inf);
  }

  deque<pair<int, int>> dq;
  {
    const int id = getId(b[0], p[0]);
    dq.emplace_back(b[0], id);
    d[b[0]][id] = 0;
  }
  while (!dq.empty()) {
    auto [x, y] = dq.front();
    dq.pop_front();

    if (x - states[x][y] >= 0) {
      const int id = getId(x - states[x][y], states[x][y]);
      if (d[x - states[x][y]][id] > d[x][y] + 1) {
        d[x - states[x][y]][id] = d[x][y] + 1;
        dq.emplace_back(x - states[x][y], id);
      }
    }

    if (x + states[x][y] < n) {
      const int id = getId(x + states[x][y], states[x][y]);
      if (d[x + states[x][y]][id] > d[x][y] + 1) {
        d[x + states[x][y]][id] = d[x][y] + 1;
        dq.emplace_back(x + states[x][y], id);
      }
    }

    if (first[x]) {
      first[x] = false;
      for (int id : can_get[x]) {
        if (d[x][y] < d[x][id]) {
          d[x][id] = d[x][y];
          dq.emplace_front(x, id);
        }
      }
    }
  }

  int ans = *min_element(d[b[1]].begin(), d[b[1]].end());
  if (ans == inf) {
    ans = -1;
  }

  cout << ans << "\n";

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43