oj.uz

Submission #826638

# Submission time Handle Problem Language Result Execution time Memory
826638 2023-08-15T18:41:51 Z cig32 Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 270 ms 222940 KB 
#include "bits/stdc++.h"
using namespace std;
#define double long double
const int MAXN = 12000000;
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 << ": "; }
int n, m, s, nxt;
pair<int, int> cmds[MAXN];
int adj[MAXN];
int id;
int ps[MAXN];
int cur[MAXN];
void add_command(int u, int v) {
  cmds[id] = {u,v};
  ps[u]++;
  id++;
}
void construct(int b, int p) { 
  for(int j=b%p; j<n; j+=p) {
    if(j+p < n) add_command(nxt + j/p, (nxt + j/p + 1) * 2 + 1); //adj[nxt + j/p].push_back((nxt + j/p + 1) * 2 + 1);
    if(j-p >= 0) add_command(nxt + j/p, (nxt + j/p - 1) * 2 + 1); //adj[nxt + j/p].push_back((nxt + j/p - 1) * 2 + 1);
    add_command(nxt + j/p, j * 2); //adj[nxt + j/p].push_back(j * 2 + 0);
  }
  add_command(b, (nxt + b/p) * 2); //adj[b].push_back((nxt + b/p) * 2 + 0);
  for(int j=b%p; j<n; j+=p) {
    nxt++;
  }
}
void solve(int tc) {
  cin >> n >> m;
  s = sqrt(n);
  nxt = n;
  int st, en;
  int bruh[s+1][s];
  for(int i=1; i<=s; i++) {
    for(int j=0; j<i; j++) {
      bruh[i][j] = -1;
    }
  }
  for(int i=0; i<m; i++) {
    int b, p;
    cin >> b >> p;
    if(i == 0) st = b;
    if(i == 1) en = b;
    if(p <= s && bruh[p][b%p] == -1) {
      bruh[p][b%p] = nxt;
      construct(b, p);
    }
    else if(p > s) {
      construct(b, p);
    }
    else {
      add_command(b, (bruh[p][b%p] + b/p) * 2);
      //adj[b].push_back((bruh[p][b%p] + b/p) * 2 + 0);
    }
  }
  for(int i=1; i<MAXN; i++) ps[i]+=ps[i-1];
  for(int i=0; i<MAXN; i++) cur[i]=ps[i]-1;
  for(int i=0; i<id; i++) {
    int u = cmds[i].first, v = cmds[i].second;
    adj[cur[u]] = v;
    cur[u]--;
  }
  int k = nxt;
  int dist[k];
  bool vis[k];
  for(int i=0; i<k; i++) dist[i] = 1e9, vis[i] = 0;
  dist[st] = 0;
  deque<int> dq;
  dq.push_back(st);
  while(dq.size()) {
    int f = dq.front();
    dq.pop_front();
    if(!vis[f]) {
      vis[f] = 1;
      int l, r;
      if(f==0) l=0, r=ps[0]-1;
      else l=ps[f-1], r=ps[f]-1;
      for(int y=l; y<=r; y++) {
        int x = adj[y];
        if(!vis[x / 2] && dist[x / 2] > dist[f] + (x % 2)) {
          dist[x / 2] = dist[f] + (x % 2);
          if(x % 2 == 0) dq.push_front(x / 2);
          else dq.push_back(x / 2);
        }
      }
    }
  }
  cout<<(dist[en]==1e9?-1:dist[en])<<"\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);
}
// 勿忘初衷

Compilation message

skyscraper.cpp: In function 'void solve(int)':
skyscraper.cpp:105:17: warning: 'en' may be used uninitialized in this function [-Wmaybe-uninitialized]
  105 |   cout<<(dist[en]==1e9?-1:dist[en])<<"\n";
      |          ~~~~~~~^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 94224 KB Output is correct
2 Correct 65 ms 94212 KB Output is correct
3 Correct 65 ms 94144 KB Output is correct
4 Correct 65 ms 94244 KB Output is correct
5 Correct 65 ms 94232 KB Output is correct
6 Correct 65 ms 94148 KB Output is correct
7 Correct 65 ms 94248 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 94232 KB Output is correct
2 Correct 67 ms 94312 KB Output is correct
3 Correct 64 ms 94156 KB Output is correct
4 Correct 65 ms 94204 KB Output is correct
5 Correct 65 ms 94156 KB Output is correct
6 Correct 72 ms 94220 KB Output is correct
7 Correct 64 ms 94196 KB Output is correct
8 Correct 68 ms 94408 KB Output is correct
9 Correct 65 ms 94180 KB Output is correct
10 Correct 66 ms 94216 KB Output is correct
11 Correct 66 ms 94356 KB Output is correct
12 Correct 66 ms 94260 KB Output is correct
13 Correct 66 ms 94288 KB Output is correct
14 Correct 64 ms 94448 KB Output is correct
15 Correct 69 ms 94612 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 94156 KB Output is correct
2 Correct 64 ms 94120 KB Output is correct
3 Correct 65 ms 94152 KB Output is correct
4 Correct 65 ms 94244 KB Output is correct
5 Correct 64 ms 94156 KB Output is correct
6 Correct 66 ms 94184 KB Output is correct
7 Correct 65 ms 94156 KB Output is correct
8 Correct 64 ms 94172 KB Output is correct
9 Correct 64 ms 94216 KB Output is correct
10 Correct 71 ms 94288 KB Output is correct
11 Correct 64 ms 94412 KB Output is correct
12 Correct 66 ms 94248 KB Output is correct
13 Correct 64 ms 94256 KB Output is correct
14 Correct 65 ms 94384 KB Output is correct
15 Correct 66 ms 94412 KB Output is correct
16 Correct 66 ms 94284 KB Output is correct
17 Correct 64 ms 94720 KB Output is correct
18 Correct 64 ms 94464 KB Output is correct
19 Correct 70 ms 94396 KB Output is correct
20 Correct 64 ms 94364 KB Output is correct
21 Correct 64 ms 94304 KB Output is correct
22 Correct 66 ms 94376 KB Output is correct
23 Correct 65 ms 94408 KB Output is correct
24 Correct 65 ms 94716 KB Output is correct
25 Correct 68 ms 94488 KB Output is correct
26 Correct 73 ms 94552 KB Output is correct
27 Correct 66 ms 94484 KB Output is correct
28 Correct 68 ms 95056 KB Output is correct
29 Correct 68 ms 96616 KB Output is correct
30 Correct 73 ms 94888 KB Output is correct
31 Correct 69 ms 95484 KB Output is correct
32 Correct 66 ms 95184 KB Output is correct
33 Correct 70 ms 98976 KB Output is correct
34 Correct 71 ms 99048 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 94192 KB Output is correct
2 Correct 72 ms 94236 KB Output is correct
3 Correct 65 ms 94128 KB Output is correct
4 Correct 66 ms 94168 KB Output is correct
5 Correct 66 ms 94176 KB Output is correct
6 Correct 69 ms 94156 KB Output is correct
7 Correct 66 ms 94140 KB Output is correct
8 Correct 65 ms 94200 KB Output is correct
9 Correct 68 ms 94296 KB Output is correct
10 Correct 65 ms 94284 KB Output is correct
11 Correct 68 ms 94436 KB Output is correct
12 Correct 66 ms 94216 KB Output is correct
13 Correct 65 ms 94164 KB Output is correct
14 Correct 66 ms 94420 KB Output is correct
15 Correct 67 ms 94420 KB Output is correct
16 Correct 70 ms 94340 KB Output is correct
17 Correct 65 ms 94752 KB Output is correct
18 Correct 65 ms 94572 KB Output is correct
19 Correct 66 ms 94328 KB Output is correct
20 Correct 65 ms 94300 KB Output is correct
21 Correct 66 ms 94260 KB Output is correct
22 Correct 67 ms 94436 KB Output is correct
23 Correct 65 ms 94388 KB Output is correct
24 Correct 67 ms 94640 KB Output is correct
25 Correct 65 ms 94496 KB Output is correct
26 Correct 65 ms 94576 KB Output is correct
27 Correct 64 ms 94424 KB Output is correct
28 Correct 67 ms 95156 KB Output is correct
29 Correct 71 ms 96672 KB Output is correct
30 Correct 66 ms 94916 KB Output is correct
31 Correct 75 ms 95520 KB Output is correct
32 Correct 67 ms 95188 KB Output is correct
33 Correct 71 ms 98944 KB Output is correct
34 Correct 71 ms 98984 KB Output is correct
35 Correct 75 ms 98124 KB Output is correct
36 Correct 66 ms 94912 KB Output is correct
37 Correct 76 ms 101308 KB Output is correct
38 Correct 77 ms 100660 KB Output is correct
39 Correct 81 ms 100692 KB Output is correct
40 Correct 77 ms 100676 KB Output is correct
41 Correct 78 ms 100624 KB Output is correct
42 Correct 68 ms 94924 KB Output is correct
43 Correct 68 ms 94792 KB Output is correct
44 Correct 69 ms 94668 KB Output is correct
45 Correct 97 ms 113276 KB Output is correct
46 Correct 97 ms 113268 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 94228 KB Output is correct
2 Correct 71 ms 94180 KB Output is correct
3 Correct 67 ms 94236 KB Output is correct
4 Correct 66 ms 94144 KB Output is correct
5 Correct 66 ms 94172 KB Output is correct
6 Correct 66 ms 94256 KB Output is correct
7 Correct 65 ms 94244 KB Output is correct
8 Correct 67 ms 94292 KB Output is correct
9 Correct 66 ms 94164 KB Output is correct
10 Correct 66 ms 94196 KB Output is correct
11 Correct 67 ms 94424 KB Output is correct
12 Correct 66 ms 94208 KB Output is correct
13 Correct 66 ms 94248 KB Output is correct
14 Correct 67 ms 94392 KB Output is correct
15 Correct 68 ms 94456 KB Output is correct
16 Correct 65 ms 94384 KB Output is correct
17 Correct 67 ms 94784 KB Output is correct
18 Correct 67 ms 94456 KB Output is correct
19 Correct 66 ms 94412 KB Output is correct
20 Correct 65 ms 94292 KB Output is correct
21 Correct 66 ms 94256 KB Output is correct
22 Correct 64 ms 94412 KB Output is correct
23 Correct 65 ms 94396 KB Output is correct
24 Correct 66 ms 94736 KB Output is correct
25 Correct 66 ms 94488 KB Output is correct
26 Correct 67 ms 94548 KB Output is correct
27 Correct 65 ms 94540 KB Output is correct
28 Correct 66 ms 95148 KB Output is correct
29 Correct 67 ms 96712 KB Output is correct
30 Correct 66 ms 94832 KB Output is correct
31 Correct 66 ms 95548 KB Output is correct
32 Correct 66 ms 95132 KB Output is correct
33 Correct 72 ms 98992 KB Output is correct
34 Correct 71 ms 99020 KB Output is correct
35 Correct 72 ms 98124 KB Output is correct
36 Correct 66 ms 94908 KB Output is correct
37 Correct 86 ms 101304 KB Output is correct
38 Correct 77 ms 100604 KB Output is correct
39 Correct 76 ms 100684 KB Output is correct
40 Correct 77 ms 100648 KB Output is correct
41 Correct 77 ms 100600 KB Output is correct
42 Correct 77 ms 94856 KB Output is correct
43 Correct 75 ms 94844 KB Output is correct
44 Correct 68 ms 94628 KB Output is correct
45 Correct 96 ms 113240 KB Output is correct
46 Correct 95 ms 113256 KB Output is correct
47 Correct 122 ms 123956 KB Output is correct
48 Correct 75 ms 103504 KB Output is correct
49 Correct 79 ms 99924 KB Output is correct
50 Correct 72 ms 100096 KB Output is correct
51 Correct 87 ms 106824 KB Output is correct
52 Correct 89 ms 107964 KB Output is correct
53 Correct 81 ms 97752 KB Output is correct
54 Correct 74 ms 95660 KB Output is correct
55 Correct 69 ms 96712 KB Output is correct
56 Correct 71 ms 96004 KB Output is correct
57 Correct 94 ms 111928 KB Output is correct
58 Correct 70 ms 97500 KB Output is correct
59 Correct 74 ms 98636 KB Output is correct
60 Correct 75 ms 100220 KB Output is correct
61 Correct 74 ms 99088 KB Output is correct
62 Correct 103 ms 113908 KB Output is correct
63 Correct 237 ms 185732 KB Output is correct
64 Correct 270 ms 206440 KB Output is correct
65 Runtime error 168 ms 222940 KB Execution killed with signal 11
66 Halted 0 ms 0 KB -