oj.uz

Submission #537386

# Submission time Handle Problem Language Result Execution time Memory
537386 2022-03-15T04:17:25 Z OrazB Jakarta Skyscrapers (APIO15_skyscraper) C++14
100 / 100
 443 ms 249616 KB 
#include <vector>
#include <list>
#include <map>
#include <set>

#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>

#define FORN(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP(X,Y,Z) for (int (X) = (Y);(X) < (Z);++(X))

#define SZ(Z) ((int)(Z).size())
#define ALL(W) (W).begin(), (W).end()
#define PB push_back

#define MP make_pair
#define A first
#define B second

#define INF 1023123123
#define EPS 1e-11

#define MX(Z,Y) Z = max((Z),(Y))
#define MN(X,Y) X = min((X),(Y))

using namespace std;

typedef long long ll;
typedef double db;
typedef vector<int> vint;

const int kMaxN = 30005;
const int kMaxSqrtN = 200;
const int kMaxAnswer = 5000000;

vector<int> powers[kMaxN];  // List of doges in a building.
vector<ll> q[kMaxAnswer];
int done[kMaxN][kMaxSqrtN];

int n, m;
ll Encode(int building, int power) {
  assert(power <= kMaxSqrtN);
  return building + power * n;
}

#ifdef DOLPHINIGLE_ENV
int main_a() {
#else
int main() {
#endif
  cin >> n >> m;
  int initial = -1, doge1 = -1;
  FORN(i, m) {
    int building, power;
    cin >> building >> power;
    powers[building].push_back(power);
    if (!i) initial = building;
    if (i == 1) doge1 = building;
  }
  int max_m = (int)sqrt(n);
  // The graph has two kinds of nodes:
  // 1) (building, power) node        printf("%02hX goes in %hu to %02hX\n", (unsigned short int)a, (unsigned short int)d, (unsigned short int)other);
  // 2) (building) node
  // We represent the second type with (building, 0).
  q[0].push_back(1LL * initial);

  int current_answer = 0;
  int best_answer = -1;
  while (current_answer < kMaxAnswer) {
    if (q[current_answer].empty()) {
      ++current_answer;
      continue;
    }
    ll top = q[current_answer].back();
    q[current_answer].pop_back();
    int building = top % n;
    int power = top / n;
    if (done[building][power]) continue;
    done[building][power] = true;

    if (building == doge1) {
      if (best_answer == -1) {
        best_answer = current_answer;
      }
      continue;
    }
    if (!power) {
      // in a building. Transition to every doges in the building that are weak, or make a jump.
      for (int doge : powers[building]) {
        if (doge <= max_m) {
          // go to doge!
          q[current_answer].push_back(Encode(building, doge));
        } else {
          // all possible locations: forward and backwards.
          for (int dir = -1; dir < 2; dir += 2) {
            for (int jumps = 1;;++jumps) {
              int pos = building + doge * dir * jumps;
              if (pos < 0 || pos >= n) break;
              q[current_answer + jumps].push_back(Encode(pos, 0));
            }
          }
        }
      }
    } else {
      // have a power.
      // Transition to building.
      q[current_answer].push_back(Encode(building, 0));
      // Jump front and back.
      int pos = building + power;
      if (pos < n) q[current_answer + 1].push_back(Encode(pos, power));
      pos = building - power;
      if (pos >= 0) q[current_answer + 1].push_back(Encode(pos, power));
    }
  }
  cout << best_answer << endl;
  return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:24:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   24 | #define FORN(X,Y) for (int (X) = 0;(X) < (Y);++(X))
      |                            ^
skyscraper.cpp:68:3: note: in expansion of macro 'FORN'
   68 |   FORN(i, m) {
      |   ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 118348 KB Output is correct
2 Correct 68 ms 118408 KB Output is correct
3 Correct 68 ms 118408 KB Output is correct
4 Correct 66 ms 118400 KB Output is correct
5 Correct 85 ms 118344 KB Output is correct
6 Correct 75 ms 118404 KB Output is correct
7 Correct 68 ms 118348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 118336 KB Output is correct
2 Correct 70 ms 118316 KB Output is correct
3 Correct 68 ms 118352 KB Output is correct
4 Correct 69 ms 118340 KB Output is correct
5 Correct 73 ms 118388 KB Output is correct
6 Correct 78 ms 118284 KB Output is correct
7 Correct 77 ms 118408 KB Output is correct
8 Correct 68 ms 118384 KB Output is correct
9 Correct 71 ms 118384 KB Output is correct
10 Correct 85 ms 118456 KB Output is correct
11 Correct 77 ms 118476 KB Output is correct
12 Correct 69 ms 118440 KB Output is correct
13 Correct 83 ms 118460 KB Output is correct
14 Correct 71 ms 118596 KB Output is correct
15 Correct 72 ms 118428 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 118292 KB Output is correct
2 Correct 69 ms 118352 KB Output is correct
3 Correct 71 ms 118348 KB Output is correct
4 Correct 67 ms 118332 KB Output is correct
5 Correct 68 ms 118344 KB Output is correct
6 Correct 72 ms 118320 KB Output is correct
7 Correct 78 ms 118384 KB Output is correct
8 Correct 76 ms 118428 KB Output is correct
9 Correct 68 ms 118420 KB Output is correct
10 Correct 79 ms 118504 KB Output is correct
11 Correct 70 ms 118504 KB Output is correct
12 Correct 75 ms 118384 KB Output is correct
13 Correct 78 ms 118420 KB Output is correct
14 Correct 80 ms 118520 KB Output is correct
15 Correct 72 ms 118428 KB Output is correct
16 Correct 72 ms 118324 KB Output is correct
17 Correct 71 ms 119176 KB Output is correct
18 Correct 71 ms 118324 KB Output is correct
19 Correct 68 ms 118376 KB Output is correct
20 Correct 72 ms 120012 KB Output is correct
21 Correct 71 ms 118348 KB Output is correct
22 Correct 68 ms 118380 KB Output is correct
23 Correct 78 ms 119776 KB Output is correct
24 Correct 83 ms 120064 KB Output is correct
25 Correct 78 ms 120052 KB Output is correct
26 Correct 75 ms 119952 KB Output is correct
27 Correct 72 ms 120092 KB Output is correct
28 Correct 71 ms 120524 KB Output is correct
29 Correct 71 ms 121248 KB Output is correct
30 Correct 71 ms 120284 KB Output is correct
31 Correct 72 ms 120656 KB Output is correct
32 Correct 73 ms 120392 KB Output is correct
33 Correct 88 ms 121924 KB Output is correct
34 Correct 72 ms 121980 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 118348 KB Output is correct
2 Correct 72 ms 118348 KB Output is correct
3 Correct 77 ms 118356 KB Output is correct
4 Correct 67 ms 118376 KB Output is correct
5 Correct 67 ms 118288 KB Output is correct
6 Correct 81 ms 118416 KB Output is correct
7 Correct 82 ms 118412 KB Output is correct
8 Correct 78 ms 118536 KB Output is correct
9 Correct 69 ms 118408 KB Output is correct
10 Correct 71 ms 118504 KB Output is correct
11 Correct 74 ms 118468 KB Output is correct
12 Correct 77 ms 118600 KB Output is correct
13 Correct 72 ms 118524 KB Output is correct
14 Correct 73 ms 118520 KB Output is correct
15 Correct 72 ms 118544 KB Output is correct
16 Correct 82 ms 118348 KB Output is correct
17 Correct 70 ms 119228 KB Output is correct
18 Correct 68 ms 118444 KB Output is correct
19 Correct 71 ms 118372 KB Output is correct
20 Correct 74 ms 120020 KB Output is correct
21 Correct 71 ms 118404 KB Output is correct
22 Correct 68 ms 118348 KB Output is correct
23 Correct 74 ms 119752 KB Output is correct
24 Correct 74 ms 120008 KB Output is correct
25 Correct 74 ms 120196 KB Output is correct
26 Correct 70 ms 120012 KB Output is correct
27 Correct 72 ms 120012 KB Output is correct
28 Correct 74 ms 120504 KB Output is correct
29 Correct 84 ms 121160 KB Output is correct
30 Correct 87 ms 120360 KB Output is correct
31 Correct 71 ms 120656 KB Output is correct
32 Correct 69 ms 120404 KB Output is correct
33 Correct 75 ms 121964 KB Output is correct
34 Correct 95 ms 121956 KB Output is correct
35 Correct 94 ms 120768 KB Output is correct
36 Correct 85 ms 119444 KB Output is correct
37 Correct 83 ms 122056 KB Output is correct
38 Correct 88 ms 121988 KB Output is correct
39 Correct 92 ms 121932 KB Output is correct
40 Correct 93 ms 122024 KB Output is correct
41 Correct 95 ms 121924 KB Output is correct
42 Correct 108 ms 120156 KB Output is correct
43 Correct 84 ms 120120 KB Output is correct
44 Correct 82 ms 120524 KB Output is correct
45 Correct 91 ms 124920 KB Output is correct
46 Correct 115 ms 125040 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 118408 KB Output is correct
2 Correct 66 ms 118404 KB Output is correct
3 Correct 66 ms 118308 KB Output is correct
4 Correct 79 ms 118320 KB Output is correct
5 Correct 76 ms 118316 KB Output is correct
6 Correct 70 ms 118416 KB Output is correct
7 Correct 68 ms 118292 KB Output is correct
8 Correct 66 ms 118428 KB Output is correct
9 Correct 68 ms 118376 KB Output is correct
10 Correct 84 ms 118396 KB Output is correct
11 Correct 84 ms 118568 KB Output is correct
12 Correct 80 ms 118496 KB Output is correct
13 Correct 71 ms 118520 KB Output is correct
14 Correct 70 ms 118484 KB Output is correct
15 Correct 68 ms 118484 KB Output is correct
16 Correct 68 ms 118380 KB Output is correct
17 Correct 76 ms 119120 KB Output is correct
18 Correct 72 ms 118384 KB Output is correct
19 Correct 70 ms 118348 KB Output is correct
20 Correct 71 ms 119988 KB Output is correct
21 Correct 68 ms 118340 KB Output is correct
22 Correct 69 ms 118416 KB Output is correct
23 Correct 77 ms 119832 KB Output is correct
24 Correct 73 ms 120112 KB Output is correct
25 Correct 69 ms 120020 KB Output is correct
26 Correct 70 ms 119988 KB Output is correct
27 Correct 72 ms 120000 KB Output is correct
28 Correct 73 ms 120560 KB Output is correct
29 Correct 75 ms 121276 KB Output is correct
30 Correct 78 ms 120352 KB Output is correct
31 Correct 72 ms 120616 KB Output is correct
32 Correct 71 ms 120328 KB Output is correct
33 Correct 77 ms 121960 KB Output is correct
34 Correct 77 ms 121992 KB Output is correct
35 Correct 100 ms 120772 KB Output is correct
36 Correct 72 ms 119436 KB Output is correct
37 Correct 83 ms 121996 KB Output is correct
38 Correct 89 ms 121956 KB Output is correct
39 Correct 94 ms 121860 KB Output is correct
40 Correct 87 ms 122028 KB Output is correct
41 Correct 91 ms 122036 KB Output is correct
42 Correct 91 ms 120160 KB Output is correct
43 Correct 83 ms 120228 KB Output is correct
44 Correct 85 ms 120592 KB Output is correct
45 Correct 90 ms 124960 KB Output is correct
46 Correct 106 ms 124864 KB Output is correct
47 Correct 123 ms 138472 KB Output is correct
48 Correct 79 ms 118764 KB Output is correct
49 Correct 90 ms 118796 KB Output is correct
50 Correct 82 ms 118780 KB Output is correct
51 Correct 122 ms 147076 KB Output is correct
52 Correct 140 ms 148044 KB Output is correct
53 Correct 104 ms 143516 KB Output is correct
54 Correct 80 ms 142344 KB Output is correct
55 Correct 82 ms 142596 KB Output is correct
56 Correct 103 ms 144012 KB Output is correct
57 Correct 127 ms 150716 KB Output is correct
58 Correct 97 ms 144328 KB Output is correct
59 Correct 105 ms 143900 KB Output is correct
60 Correct 108 ms 143888 KB Output is correct
61 Correct 107 ms 144076 KB Output is correct
62 Correct 149 ms 156564 KB Output is correct
63 Correct 141 ms 162564 KB Output is correct
64 Correct 153 ms 166704 KB Output is correct
65 Correct 244 ms 186592 KB Output is correct
66 Correct 443 ms 249616 KB Output is correct
67 Correct 408 ms 248768 KB Output is correct