// Authored by dolphinigle
#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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
134 ms |
118464 KB |
Output is correct |
2 |
Correct |
134 ms |
118396 KB |
Output is correct |
3 |
Correct |
134 ms |
118460 KB |
Output is correct |
4 |
Correct |
132 ms |
118492 KB |
Output is correct |
5 |
Correct |
133 ms |
118504 KB |
Output is correct |
6 |
Correct |
132 ms |
118488 KB |
Output is correct |
7 |
Correct |
132 ms |
118392 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
134 ms |
118384 KB |
Output is correct |
2 |
Correct |
134 ms |
118520 KB |
Output is correct |
3 |
Correct |
135 ms |
118496 KB |
Output is correct |
4 |
Correct |
132 ms |
118484 KB |
Output is correct |
5 |
Correct |
126 ms |
118488 KB |
Output is correct |
6 |
Correct |
133 ms |
118392 KB |
Output is correct |
7 |
Correct |
134 ms |
118396 KB |
Output is correct |
8 |
Correct |
137 ms |
118464 KB |
Output is correct |
9 |
Correct |
138 ms |
118520 KB |
Output is correct |
10 |
Correct |
141 ms |
118472 KB |
Output is correct |
11 |
Correct |
136 ms |
118532 KB |
Output is correct |
12 |
Correct |
137 ms |
118648 KB |
Output is correct |
13 |
Correct |
138 ms |
118480 KB |
Output is correct |
14 |
Correct |
140 ms |
118620 KB |
Output is correct |
15 |
Correct |
137 ms |
118648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
118492 KB |
Output is correct |
2 |
Correct |
141 ms |
118380 KB |
Output is correct |
3 |
Correct |
135 ms |
118396 KB |
Output is correct |
4 |
Correct |
135 ms |
118364 KB |
Output is correct |
5 |
Correct |
136 ms |
118424 KB |
Output is correct |
6 |
Correct |
136 ms |
118520 KB |
Output is correct |
7 |
Correct |
139 ms |
118680 KB |
Output is correct |
8 |
Correct |
140 ms |
118392 KB |
Output is correct |
9 |
Correct |
134 ms |
118588 KB |
Output is correct |
10 |
Correct |
135 ms |
118540 KB |
Output is correct |
11 |
Correct |
142 ms |
118520 KB |
Output is correct |
12 |
Correct |
141 ms |
118520 KB |
Output is correct |
13 |
Correct |
141 ms |
118576 KB |
Output is correct |
14 |
Correct |
142 ms |
118520 KB |
Output is correct |
15 |
Correct |
140 ms |
118648 KB |
Output is correct |
16 |
Correct |
141 ms |
118520 KB |
Output is correct |
17 |
Correct |
141 ms |
119288 KB |
Output is correct |
18 |
Correct |
141 ms |
118496 KB |
Output is correct |
19 |
Correct |
135 ms |
118520 KB |
Output is correct |
20 |
Correct |
142 ms |
120156 KB |
Output is correct |
21 |
Correct |
140 ms |
118500 KB |
Output is correct |
22 |
Correct |
135 ms |
118392 KB |
Output is correct |
23 |
Correct |
138 ms |
119928 KB |
Output is correct |
24 |
Correct |
146 ms |
120176 KB |
Output is correct |
25 |
Correct |
144 ms |
120056 KB |
Output is correct |
26 |
Correct |
143 ms |
120064 KB |
Output is correct |
27 |
Correct |
144 ms |
120168 KB |
Output is correct |
28 |
Correct |
143 ms |
120608 KB |
Output is correct |
29 |
Correct |
145 ms |
121344 KB |
Output is correct |
30 |
Correct |
141 ms |
120404 KB |
Output is correct |
31 |
Correct |
138 ms |
120696 KB |
Output is correct |
32 |
Correct |
142 ms |
120476 KB |
Output is correct |
33 |
Correct |
152 ms |
122060 KB |
Output is correct |
34 |
Correct |
152 ms |
122000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
140 ms |
118480 KB |
Output is correct |
2 |
Correct |
138 ms |
118408 KB |
Output is correct |
3 |
Correct |
139 ms |
118480 KB |
Output is correct |
4 |
Correct |
137 ms |
118412 KB |
Output is correct |
5 |
Correct |
139 ms |
118492 KB |
Output is correct |
6 |
Correct |
135 ms |
118384 KB |
Output is correct |
7 |
Correct |
139 ms |
118516 KB |
Output is correct |
8 |
Correct |
139 ms |
118392 KB |
Output is correct |
9 |
Correct |
135 ms |
118480 KB |
Output is correct |
10 |
Correct |
138 ms |
118572 KB |
Output is correct |
11 |
Correct |
135 ms |
118520 KB |
Output is correct |
12 |
Correct |
145 ms |
118648 KB |
Output is correct |
13 |
Correct |
139 ms |
118612 KB |
Output is correct |
14 |
Correct |
136 ms |
118648 KB |
Output is correct |
15 |
Correct |
138 ms |
118520 KB |
Output is correct |
16 |
Correct |
133 ms |
118392 KB |
Output is correct |
17 |
Correct |
140 ms |
119220 KB |
Output is correct |
18 |
Correct |
141 ms |
118392 KB |
Output is correct |
19 |
Correct |
148 ms |
118520 KB |
Output is correct |
20 |
Correct |
139 ms |
120212 KB |
Output is correct |
21 |
Correct |
134 ms |
118532 KB |
Output is correct |
22 |
Correct |
134 ms |
118520 KB |
Output is correct |
23 |
Correct |
137 ms |
119936 KB |
Output is correct |
24 |
Correct |
138 ms |
120188 KB |
Output is correct |
25 |
Correct |
136 ms |
120108 KB |
Output is correct |
26 |
Correct |
142 ms |
120112 KB |
Output is correct |
27 |
Correct |
139 ms |
120056 KB |
Output is correct |
28 |
Correct |
144 ms |
120736 KB |
Output is correct |
29 |
Correct |
143 ms |
121336 KB |
Output is correct |
30 |
Correct |
142 ms |
120380 KB |
Output is correct |
31 |
Correct |
144 ms |
120696 KB |
Output is correct |
32 |
Correct |
142 ms |
120568 KB |
Output is correct |
33 |
Correct |
151 ms |
122104 KB |
Output is correct |
34 |
Correct |
149 ms |
121980 KB |
Output is correct |
35 |
Correct |
164 ms |
120848 KB |
Output is correct |
36 |
Correct |
140 ms |
119476 KB |
Output is correct |
37 |
Correct |
163 ms |
122076 KB |
Output is correct |
38 |
Correct |
172 ms |
121980 KB |
Output is correct |
39 |
Correct |
168 ms |
121980 KB |
Output is correct |
40 |
Correct |
170 ms |
122096 KB |
Output is correct |
41 |
Correct |
188 ms |
122024 KB |
Output is correct |
42 |
Correct |
166 ms |
120356 KB |
Output is correct |
43 |
Correct |
159 ms |
120204 KB |
Output is correct |
44 |
Correct |
164 ms |
120640 KB |
Output is correct |
45 |
Correct |
181 ms |
124976 KB |
Output is correct |
46 |
Correct |
176 ms |
124892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
133 ms |
118396 KB |
Output is correct |
2 |
Correct |
133 ms |
118432 KB |
Output is correct |
3 |
Correct |
134 ms |
118372 KB |
Output is correct |
4 |
Correct |
133 ms |
118392 KB |
Output is correct |
5 |
Correct |
134 ms |
118412 KB |
Output is correct |
6 |
Correct |
146 ms |
118392 KB |
Output is correct |
7 |
Correct |
133 ms |
118416 KB |
Output is correct |
8 |
Correct |
133 ms |
118492 KB |
Output is correct |
9 |
Correct |
135 ms |
118560 KB |
Output is correct |
10 |
Correct |
133 ms |
118520 KB |
Output is correct |
11 |
Correct |
132 ms |
118740 KB |
Output is correct |
12 |
Correct |
134 ms |
118520 KB |
Output is correct |
13 |
Correct |
133 ms |
118776 KB |
Output is correct |
14 |
Correct |
137 ms |
118604 KB |
Output is correct |
15 |
Correct |
136 ms |
118620 KB |
Output is correct |
16 |
Correct |
133 ms |
118392 KB |
Output is correct |
17 |
Correct |
136 ms |
119260 KB |
Output is correct |
18 |
Correct |
133 ms |
118460 KB |
Output is correct |
19 |
Correct |
133 ms |
118520 KB |
Output is correct |
20 |
Correct |
138 ms |
120184 KB |
Output is correct |
21 |
Correct |
134 ms |
118520 KB |
Output is correct |
22 |
Correct |
134 ms |
118504 KB |
Output is correct |
23 |
Correct |
136 ms |
119896 KB |
Output is correct |
24 |
Correct |
137 ms |
120188 KB |
Output is correct |
25 |
Correct |
141 ms |
120072 KB |
Output is correct |
26 |
Correct |
138 ms |
120184 KB |
Output is correct |
27 |
Correct |
144 ms |
120136 KB |
Output is correct |
28 |
Correct |
148 ms |
120624 KB |
Output is correct |
29 |
Correct |
146 ms |
121308 KB |
Output is correct |
30 |
Correct |
142 ms |
120440 KB |
Output is correct |
31 |
Correct |
146 ms |
120824 KB |
Output is correct |
32 |
Correct |
145 ms |
120404 KB |
Output is correct |
33 |
Correct |
151 ms |
122104 KB |
Output is correct |
34 |
Correct |
152 ms |
121988 KB |
Output is correct |
35 |
Correct |
166 ms |
120804 KB |
Output is correct |
36 |
Correct |
143 ms |
119700 KB |
Output is correct |
37 |
Correct |
166 ms |
122240 KB |
Output is correct |
38 |
Correct |
173 ms |
122072 KB |
Output is correct |
39 |
Correct |
175 ms |
121992 KB |
Output is correct |
40 |
Correct |
171 ms |
122160 KB |
Output is correct |
41 |
Correct |
172 ms |
122088 KB |
Output is correct |
42 |
Correct |
160 ms |
120280 KB |
Output is correct |
43 |
Correct |
160 ms |
120376 KB |
Output is correct |
44 |
Correct |
161 ms |
120924 KB |
Output is correct |
45 |
Correct |
180 ms |
125044 KB |
Output is correct |
46 |
Correct |
179 ms |
124888 KB |
Output is correct |
47 |
Correct |
245 ms |
138824 KB |
Output is correct |
48 |
Correct |
164 ms |
119032 KB |
Output is correct |
49 |
Correct |
160 ms |
118872 KB |
Output is correct |
50 |
Correct |
156 ms |
118876 KB |
Output is correct |
51 |
Correct |
240 ms |
147192 KB |
Output is correct |
52 |
Correct |
246 ms |
147984 KB |
Output is correct |
53 |
Correct |
207 ms |
143352 KB |
Output is correct |
54 |
Correct |
168 ms |
142320 KB |
Output is correct |
55 |
Correct |
174 ms |
142792 KB |
Output is correct |
56 |
Correct |
204 ms |
143864 KB |
Output is correct |
57 |
Correct |
232 ms |
150840 KB |
Output is correct |
58 |
Correct |
194 ms |
144328 KB |
Output is correct |
59 |
Correct |
199 ms |
143868 KB |
Output is correct |
60 |
Correct |
214 ms |
143864 KB |
Output is correct |
61 |
Correct |
206 ms |
144028 KB |
Output is correct |
62 |
Correct |
304 ms |
156468 KB |
Output is correct |
63 |
Correct |
299 ms |
162612 KB |
Output is correct |
64 |
Correct |
324 ms |
166744 KB |
Output is correct |
65 |
Correct |
502 ms |
186692 KB |
Output is correct |
66 |
Correct |
871 ms |
248944 KB |
Output is correct |
67 |
Correct |
849 ms |
246260 KB |
Output is correct |