oj.uz

Submission #550137

# Submission time Handle Problem Language Result Execution time Memory
550137 2022-04-17T10:31:45 Z Soumya1 Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 4 ms 4820 KB 
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 30'000;
vector<int> all[mxN], init[mxN], l[mxN];
vector<int> dist[mxN];
bool vis[mxN];
int idx(int i, int j) {
  if (j < 200) return j;
  return lower_bound(all[i].begin(), all[i].end(), j) - all[i].begin();
}
void testCase() {
  int n, m;
  cin >> n >> m;
  vector<int> v;
  while (m--) {
    int b, p;
    cin >> b >> p;
    v.push_back(b);
    init[b].push_back(p);
    l[b % p].push_back(p);
  }
  for (int i = 0; i < n; i++) {
    sort(l[i].begin(), l[i].end());
    sort(init[i].begin(), init[i].end());
    init[i].erase(unique(init[i].begin(), init[i].end()), init[i].end());
    l[i].erase(unique(l[i].begin(), l[i].end()), l[i].end());
  }
  for (int i = 0; i < n; i++) {
    for (int j : l[i]) {
      if (j < 200) continue;
      for (int k = i; k < n; k += j) {
        all[k].push_back(j);
      }
    }
    sort(all[i].begin(), all[i].end());
    dist[i].assign(all[i].size() + 200, 1e9);
  }
  queue<tuple<int, int, int>> q;
  for (auto p : init[v[0]]) {
    vis[v[0]] = true;
    int vv = idx(v[0], p);
    q.push({v[0], p, vv});
    dist[v[0]][vv] = 0;
  }
  while (!q.empty()) {
    auto [u, p, id] = q.front();
    q.pop();
    int i;
    if (u + p < n) i = idx(u + p, p);
    if (u + p < n && dist[u + p][i] == 1e9) {
      dist[u + p][i] = dist[u][id] + 1;
      q.push({u + p, p, i});
    }
    if (u + p < n && !vis[u + p]) {
      vis[u + p] = true;
      for (int pp : init[u + p]) {
        i = idx(u + p, pp);
        if (dist[u + p][i] == 1e9) {
          dist[u + p][i] = dist[u][id] + 1;
          q.push({u + p, pp, i});
        }
      }
    }
    if (u - p >= 0) i = idx(u - p, p);
    if (u - p >= 0 && dist[u - p][i] == 1e9) {
      dist[u - p][i] = dist[u][id] + 1;
      q.push({u - p, p, i});
    }
    if (u - p >= 0 && !vis[u - p]) {
      vis[u - p] = true;
      for (int pp : init[u - p]) {
        i = idx(u - p, pp);
        if (dist[u - p][i] == 1e9) {
          dist[u - p][i] = dist[u][id] + 1;
          q.push({u - p, pp, i});
        }
      }
    }
  }
  int ans = *min_element(dist[v[1]].begin(), dist[v[1]].end());
  cout << (ans == 1e9 ? -1 : ans) << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3080 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 2 ms 3156 KB Output is correct
7 Correct 2 ms 3104 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 3 ms 3028 KB Output is correct
3 Correct 1 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 2 ms 3156 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 2 ms 3284 KB Output is correct
12 Correct 3 ms 3156 KB Output is correct
13 Correct 2 ms 3156 KB Output is correct
14 Correct 2 ms 3284 KB Output is correct
15 Correct 2 ms 3284 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3156 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 2 ms 3100 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Correct 1 ms 3156 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 2 ms 3284 KB Output is correct
12 Correct 2 ms 3156 KB Output is correct
13 Correct 2 ms 3156 KB Output is correct
14 Correct 2 ms 3284 KB Output is correct
15 Correct 3 ms 3284 KB Output is correct
16 Correct 2 ms 3284 KB Output is correct
17 Correct 4 ms 3796 KB Output is correct
18 Correct 3 ms 4564 KB Output is correct
19 Correct 3 ms 4692 KB Output is correct
20 Correct 3 ms 4820 KB Output is correct
21 Correct 2 ms 3424 KB Output is correct
22 Correct 3 ms 4564 KB Output is correct
23 Correct 3 ms 4436 KB Output is correct
24 Correct 4 ms 4820 KB Output is correct
25 Correct 3 ms 4820 KB Output is correct
26 Correct 3 ms 4692 KB Output is correct
27 Correct 4 ms 4692 KB Output is correct
28 Incorrect 4 ms 4820 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 1 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 1 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 1 ms 3136 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 2 ms 3156 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 3 ms 3284 KB Output is correct
12 Correct 2 ms 3156 KB Output is correct
13 Correct 2 ms 3156 KB Output is correct
14 Correct 2 ms 3284 KB Output is correct
15 Correct 2 ms 3284 KB Output is correct
16 Correct 2 ms 3284 KB Output is correct
17 Correct 3 ms 3796 KB Output is correct
18 Correct 3 ms 4564 KB Output is correct
19 Correct 3 ms 4692 KB Output is correct
20 Correct 3 ms 4820 KB Output is correct
21 Correct 2 ms 3412 KB Output is correct
22 Correct 3 ms 4564 KB Output is correct
23 Correct 3 ms 4436 KB Output is correct
24 Correct 4 ms 4820 KB Output is correct
25 Correct 3 ms 4820 KB Output is correct
26 Correct 3 ms 4692 KB Output is correct
27 Correct 3 ms 4684 KB Output is correct
28 Incorrect 4 ms 4820 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3140 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 1 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 2 ms 3156 KB Output is correct
9 Correct 2 ms 3156 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 2 ms 3284 KB Output is correct
12 Correct 2 ms 3156 KB Output is correct
13 Correct 2 ms 3156 KB Output is correct
14 Correct 2 ms 3284 KB Output is correct
15 Correct 2 ms 3284 KB Output is correct
16 Correct 2 ms 3284 KB Output is correct
17 Correct 3 ms 3796 KB Output is correct
18 Correct 3 ms 4564 KB Output is correct
19 Correct 3 ms 4692 KB Output is correct
20 Correct 3 ms 4820 KB Output is correct
21 Correct 2 ms 3412 KB Output is correct
22 Correct 3 ms 4564 KB Output is correct
23 Correct 3 ms 4436 KB Output is correct
24 Correct 4 ms 4820 KB Output is correct
25 Correct 3 ms 4820 KB Output is correct
26 Correct 3 ms 4692 KB Output is correct
27 Correct 3 ms 4692 KB Output is correct
28 Incorrect 4 ms 4820 KB Output isn't correct
29 Halted 0 ms 0 KB -