oj.uz

Submission #826510

# Submission time Handle Problem Language Result Execution time Memory
826510 2023-08-15T16:11:23 Z vjudge1 Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 149 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;
#define double long double
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
vector<pair<int, bool> >adj[10400000];
void solve(int tc) {
  int n, m;
  cin >> n >> m;
  int s = sqrt(n);
  int b[m], p[m];
  for(int i=0; i<m; i++) cin >> b[i] >> p[i];
  int nxt = (s+1) * n;
  for(int i=1; i<=s; i++) {
    for(int j=i*n; j<(i+1)*n; j++) {
      if(j+i < (i+1)*n) adj[j].push_back({j+i, 1});
      if(j-i >= i*n) adj[j].push_back({j-i, 1});
      adj[j].push_back({j%n, 0});
    }
  }
  for(int i=0; i<m; i++) {
    if(p[i] <= s) adj[b[i]].push_back({b[i]+p[i]*n, 0});
    else {
      for(int j=b[i]%p[i]; j<n; j+=p[i]) {
        if(j+p[i] < n) adj[nxt + j/p[i]].push_back({nxt + j/p[i] + 1, 1});
        if(j-p[i] >= 0) adj[nxt + j/p[i]].push_back({nxt + j/p[i] - 1, 1});
        adj[nxt + j/p[i]].push_back({j, 0});
      }
      adj[b[i]].push_back({nxt + b[i]/p[i], 0});
      for(int j=b[i]%p[i]; j<n; j+=p[i]) {
        nxt++;
      }
    }
  }
  int k = nxt;
  int dist[k];
  bool vis[k];
  for(int i=0; i<k; i++) dist[i] = 1e9, vis[i] = 0;
  dist[b[0]] = 0;
  deque<int> dq;
  dq.push_back(b[0]);
  while(dq.size()) {
    int f = dq.front();
    dq.pop_front();
    if(!vis[f]) {
      vis[f] = 1;
      for(pair<int, int> x: adj[f]) {
        if(!vis[x.first] && dist[x.first] > dist[f] + x.second) {
          dist[x.first] = dist[f] + x.second;
          if(x.second == 0) dq.push_front(x.first);
          else dq.push_back(x.first);
        }
      }
    }
  }
  cout<<(dist[b[1]]==1e9?-1:dist[b[1]])<<"\n";
}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// 勿忘初衷

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 244492 KB Output is correct
2 Correct 106 ms 244428 KB Output is correct
3 Correct 110 ms 244684 KB Output is correct
4 Correct 109 ms 244512 KB Output is correct
5 Correct 106 ms 244492 KB Output is correct
6 Correct 109 ms 244480 KB Output is correct
7 Correct 140 ms 244444 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 244448 KB Output is correct
2 Correct 109 ms 244428 KB Output is correct
3 Correct 111 ms 244528 KB Output is correct
4 Correct 110 ms 244468 KB Output is correct
5 Correct 109 ms 244504 KB Output is correct
6 Correct 115 ms 244444 KB Output is correct
7 Correct 110 ms 244452 KB Output is correct
8 Correct 110 ms 244504 KB Output is correct
9 Correct 109 ms 244564 KB Output is correct
10 Correct 111 ms 244584 KB Output is correct
11 Correct 110 ms 244812 KB Output is correct
12 Correct 109 ms 244604 KB Output is correct
13 Correct 110 ms 244608 KB Output is correct
14 Correct 111 ms 244772 KB Output is correct
15 Correct 120 ms 244844 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 244440 KB Output is correct
2 Correct 111 ms 244452 KB Output is correct
3 Correct 111 ms 244524 KB Output is correct
4 Correct 112 ms 244420 KB Output is correct
5 Correct 113 ms 244472 KB Output is correct
6 Correct 112 ms 244436 KB Output is correct
7 Correct 108 ms 244448 KB Output is correct
8 Correct 110 ms 244464 KB Output is correct
9 Correct 110 ms 244520 KB Output is correct
10 Correct 120 ms 244708 KB Output is correct
11 Correct 112 ms 244716 KB Output is correct
12 Correct 112 ms 244580 KB Output is correct
13 Correct 111 ms 244632 KB Output is correct
14 Correct 114 ms 244844 KB Output is correct
15 Correct 109 ms 244812 KB Output is correct
16 Correct 110 ms 244676 KB Output is correct
17 Correct 113 ms 245880 KB Output is correct
18 Correct 118 ms 248392 KB Output is correct
19 Correct 122 ms 249180 KB Output is correct
20 Correct 117 ms 249088 KB Output is correct
21 Correct 108 ms 244972 KB Output is correct
22 Correct 123 ms 248480 KB Output is correct
23 Correct 115 ms 247928 KB Output is correct
24 Correct 120 ms 249036 KB Output is correct
25 Correct 119 ms 249292 KB Output is correct
26 Correct 120 ms 249164 KB Output is correct
27 Correct 119 ms 249176 KB Output is correct
28 Correct 127 ms 249552 KB Output is correct
29 Correct 122 ms 249164 KB Output is correct
30 Correct 120 ms 249028 KB Output is correct
31 Correct 120 ms 249156 KB Output is correct
32 Correct 119 ms 249632 KB Output is correct
33 Correct 127 ms 251052 KB Output is correct
34 Correct 122 ms 251104 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 244512 KB Output is correct
2 Correct 111 ms 244532 KB Output is correct
3 Correct 110 ms 244496 KB Output is correct
4 Correct 111 ms 244472 KB Output is correct
5 Correct 115 ms 244512 KB Output is correct
6 Correct 119 ms 244512 KB Output is correct
7 Correct 122 ms 244524 KB Output is correct
8 Correct 118 ms 244464 KB Output is correct
9 Correct 111 ms 244552 KB Output is correct
10 Correct 111 ms 244556 KB Output is correct
11 Correct 112 ms 244824 KB Output is correct
12 Correct 113 ms 244540 KB Output is correct
13 Correct 117 ms 244828 KB Output is correct
14 Correct 114 ms 244828 KB Output is correct
15 Correct 111 ms 244800 KB Output is correct
16 Correct 112 ms 244724 KB Output is correct
17 Correct 116 ms 245920 KB Output is correct
18 Correct 120 ms 248432 KB Output is correct
19 Correct 119 ms 249196 KB Output is correct
20 Correct 119 ms 249128 KB Output is correct
21 Correct 112 ms 245012 KB Output is correct
22 Correct 117 ms 248524 KB Output is correct
23 Correct 125 ms 247860 KB Output is correct
24 Correct 118 ms 249124 KB Output is correct
25 Correct 119 ms 249304 KB Output is correct
26 Correct 121 ms 249216 KB Output is correct
27 Correct 119 ms 249164 KB Output is correct
28 Correct 120 ms 249588 KB Output is correct
29 Correct 117 ms 249024 KB Output is correct
30 Correct 119 ms 248980 KB Output is correct
31 Correct 119 ms 249176 KB Output is correct
32 Correct 122 ms 249652 KB Output is correct
33 Correct 127 ms 251072 KB Output is correct
34 Correct 123 ms 251100 KB Output is correct
35 Correct 130 ms 251224 KB Output is correct
36 Correct 116 ms 246892 KB Output is correct
37 Correct 145 ms 255584 KB Output is correct
38 Correct 139 ms 255276 KB Output is correct
39 Correct 142 ms 255268 KB Output is correct
40 Correct 139 ms 255232 KB Output is correct
41 Correct 143 ms 255420 KB Output is correct
42 Correct 123 ms 249988 KB Output is correct
43 Correct 122 ms 249884 KB Output is correct
44 Correct 123 ms 249840 KB Output is correct
45 Runtime error 128 ms 262144 KB Execution killed with signal 9
46 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 244500 KB Output is correct
2 Correct 111 ms 244540 KB Output is correct
3 Correct 111 ms 244476 KB Output is correct
4 Correct 112 ms 244404 KB Output is correct
5 Correct 111 ms 244484 KB Output is correct
6 Correct 111 ms 244504 KB Output is correct
7 Correct 110 ms 244432 KB Output is correct
8 Correct 111 ms 244432 KB Output is correct
9 Correct 112 ms 244524 KB Output is correct
10 Correct 112 ms 244616 KB Output is correct
11 Correct 113 ms 244768 KB Output is correct
12 Correct 113 ms 244560 KB Output is correct
13 Correct 112 ms 244532 KB Output is correct
14 Correct 114 ms 244796 KB Output is correct
15 Correct 124 ms 244852 KB Output is correct
16 Correct 113 ms 244728 KB Output is correct
17 Correct 115 ms 245872 KB Output is correct
18 Correct 119 ms 248328 KB Output is correct
19 Correct 122 ms 249372 KB Output is correct
20 Correct 121 ms 249160 KB Output is correct
21 Correct 112 ms 244940 KB Output is correct
22 Correct 117 ms 248516 KB Output is correct
23 Correct 117 ms 247880 KB Output is correct
24 Correct 120 ms 249044 KB Output is correct
25 Correct 120 ms 249296 KB Output is correct
26 Correct 121 ms 249164 KB Output is correct
27 Correct 118 ms 249152 KB Output is correct
28 Correct 123 ms 249580 KB Output is correct
29 Correct 119 ms 249068 KB Output is correct
30 Correct 118 ms 249036 KB Output is correct
31 Correct 121 ms 249152 KB Output is correct
32 Correct 125 ms 249676 KB Output is correct
33 Correct 126 ms 251056 KB Output is correct
34 Correct 124 ms 251096 KB Output is correct
35 Correct 127 ms 251348 KB Output is correct
36 Correct 121 ms 246924 KB Output is correct
37 Correct 146 ms 255488 KB Output is correct
38 Correct 141 ms 255296 KB Output is correct
39 Correct 139 ms 255180 KB Output is correct
40 Correct 143 ms 255336 KB Output is correct
41 Correct 149 ms 255288 KB Output is correct
42 Correct 123 ms 250032 KB Output is correct
43 Correct 122 ms 249840 KB Output is correct
44 Correct 123 ms 249860 KB Output is correct
45 Runtime error 124 ms 262144 KB Execution killed with signal 9
46 Halted 0 ms 0 KB -