oj.uz

Submission #550132

# Submission time Handle Problem Language Result Execution time Memory
550132 2022-04-17T10:26:29 Z Soumya1 Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 1000 ms 48660 KB 
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
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) {
  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());
    all[i] = l[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j : l[i]) {
      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(), 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});
        }
      }
    }
  }
  dist[v[1]].push_back(1e9);
  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;
}

Compilation message

skyscraper.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

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 3028 KB Output is correct
3 Correct 2 ms 3028 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 3 ms 3028 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3028 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 2 ms 3028 KB Output is correct
3 Correct 3 ms 3028 KB Output is correct
4 Correct 1 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 3064 KB Output is correct
8 Correct 2 ms 3028 KB Output is correct
9 Correct 1 ms 3156 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 3 ms 3156 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

Subtask #3
14.0 / 14.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 2 ms 3028 KB Output is correct
4 Correct 2 ms 3024 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 2 ms 3028 KB Output is correct
9 Correct 2 ms 3156 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 4 ms 3156 KB Output is correct
12 Correct 2 ms 3156 KB Output is correct
13 Correct 2 ms 3156 KB Output is correct
14 Correct 3 ms 3284 KB Output is correct
15 Correct 3 ms 3284 KB Output is correct
16 Correct 2 ms 3156 KB Output is correct
17 Correct 4 ms 3284 KB Output is correct
18 Correct 3 ms 3284 KB Output is correct
19 Correct 2 ms 3284 KB Output is correct
20 Correct 2 ms 3284 KB Output is correct
21 Correct 2 ms 3156 KB Output is correct
22 Correct 2 ms 3284 KB Output is correct
23 Correct 3 ms 3284 KB Output is correct
24 Correct 4 ms 3412 KB Output is correct
25 Correct 3 ms 3284 KB Output is correct
26 Correct 3 ms 3284 KB Output is correct
27 Correct 3 ms 3284 KB Output is correct
28 Correct 5 ms 3568 KB Output is correct
29 Correct 8 ms 3768 KB Output is correct
30 Correct 3 ms 3284 KB Output is correct
31 Correct 5 ms 3548 KB Output is correct
32 Correct 4 ms 3412 KB Output is correct
33 Correct 17 ms 4320 KB Output is correct
34 Correct 17 ms 4264 KB Output is correct

Subtask #4
21.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 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 3 ms 3028 KB Output is correct
7 Correct 3 ms 3028 KB Output is correct
8 Correct 2 ms 3028 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 3156 KB Output is correct
12 Correct 2 ms 3156 KB Output is correct
13 Correct 2 ms 3156 KB Output is correct
14 Correct 3 ms 3284 KB Output is correct
15 Correct 3 ms 3284 KB Output is correct
16 Correct 3 ms 3156 KB Output is correct
17 Correct 4 ms 3284 KB Output is correct
18 Correct 2 ms 3284 KB Output is correct
19 Correct 2 ms 3284 KB Output is correct
20 Correct 3 ms 3284 KB Output is correct
21 Correct 2 ms 3156 KB Output is correct
22 Correct 2 ms 3284 KB Output is correct
23 Correct 3 ms 3284 KB Output is correct
24 Correct 4 ms 3412 KB Output is correct
25 Correct 3 ms 3284 KB Output is correct
26 Correct 3 ms 3284 KB Output is correct
27 Correct 3 ms 3284 KB Output is correct
28 Correct 4 ms 3540 KB Output is correct
29 Correct 8 ms 3768 KB Output is correct
30 Correct 3 ms 3284 KB Output is correct
31 Correct 5 ms 3540 KB Output is correct
32 Correct 4 ms 3412 KB Output is correct
33 Correct 17 ms 4308 KB Output is correct
34 Correct 17 ms 4320 KB Output is correct
35 Correct 22 ms 5204 KB Output is correct
36 Correct 5 ms 3540 KB Output is correct
37 Correct 35 ms 5692 KB Output is correct
38 Correct 34 ms 5972 KB Output is correct
39 Correct 35 ms 6040 KB Output is correct
40 Correct 34 ms 6028 KB Output is correct
41 Correct 33 ms 5972 KB Output is correct
42 Correct 7 ms 3668 KB Output is correct
43 Correct 7 ms 3592 KB Output is correct
44 Correct 7 ms 3668 KB Output is correct
45 Correct 78 ms 8520 KB Output is correct
46 Correct 77 ms 8420 KB Output is correct

Subtask #5
0 / 43.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 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 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 2 ms 3028 KB Output is correct
9 Correct 2 ms 3028 KB Output is correct
10 Correct 2 ms 3156 KB Output is correct
11 Correct 3 ms 3156 KB Output is correct
12 Correct 2 ms 3148 KB Output is correct
13 Correct 2 ms 3156 KB Output is correct
14 Correct 3 ms 3284 KB Output is correct
15 Correct 3 ms 3284 KB Output is correct
16 Correct 2 ms 3156 KB Output is correct
17 Correct 4 ms 3284 KB Output is correct
18 Correct 3 ms 3284 KB Output is correct
19 Correct 2 ms 3284 KB Output is correct
20 Correct 2 ms 3284 KB Output is correct
21 Correct 2 ms 3156 KB Output is correct
22 Correct 2 ms 3284 KB Output is correct
23 Correct 3 ms 3284 KB Output is correct
24 Correct 4 ms 3412 KB Output is correct
25 Correct 3 ms 3284 KB Output is correct
26 Correct 3 ms 3284 KB Output is correct
27 Correct 3 ms 3284 KB Output is correct
28 Correct 4 ms 3540 KB Output is correct
29 Correct 8 ms 3668 KB Output is correct
30 Correct 3 ms 3284 KB Output is correct
31 Correct 5 ms 3540 KB Output is correct
32 Correct 4 ms 3412 KB Output is correct
33 Correct 17 ms 4308 KB Output is correct
34 Correct 18 ms 4316 KB Output is correct
35 Correct 22 ms 5252 KB Output is correct
36 Correct 5 ms 3544 KB Output is correct
37 Correct 34 ms 5800 KB Output is correct
38 Correct 34 ms 6076 KB Output is correct
39 Correct 32 ms 5972 KB Output is correct
40 Correct 33 ms 5964 KB Output is correct
41 Correct 34 ms 6040 KB Output is correct
42 Correct 7 ms 3604 KB Output is correct
43 Correct 8 ms 3656 KB Output is correct
44 Correct 7 ms 3668 KB Output is correct
45 Correct 80 ms 8400 KB Output is correct
46 Correct 76 ms 8392 KB Output is correct
47 Correct 158 ms 11940 KB Output is correct
48 Correct 21 ms 7152 KB Output is correct
49 Correct 18 ms 6324 KB Output is correct
50 Correct 16 ms 6136 KB Output is correct
51 Correct 68 ms 8604 KB Output is correct
52 Correct 72 ms 8908 KB Output is correct
53 Correct 22 ms 6640 KB Output is correct
54 Correct 5 ms 4948 KB Output is correct
55 Correct 6 ms 4948 KB Output is correct
56 Correct 12 ms 6144 KB Output is correct
57 Correct 54 ms 7928 KB Output is correct
58 Correct 11 ms 5460 KB Output is correct
59 Correct 16 ms 5424 KB Output is correct
60 Correct 21 ms 5588 KB Output is correct
61 Correct 18 ms 5736 KB Output is correct
62 Correct 76 ms 10832 KB Output is correct
63 Correct 614 ms 28944 KB Output is correct
64 Correct 770 ms 32208 KB Output is correct
65 Execution timed out 1092 ms 48660 KB Time limit exceeded
66 Halted 0 ms 0 KB -