/**
* Method: interpolate altitudes using all integers in between, then run a
* breadth-first search.
*
* Author: Catalin Francu
*
* Details: When reading data, suppress consecutive equal altitudes and
* interpolate consecutive altitudes like x y into x x+1 ... y-1 y, so that
* every two consecutive altitudes differ by 1.
*
* As with Dijkstra's algorithm, we treat this as a graph. However, all edges
* now have a weight of 1, so we can use a much simpler breadth-first search.
*
* This algorithm creates O(N*H) interpolated altitudes, where H is the
* maximum altitude. Thus the overall algorithm requires O(N^2 * H^2) time and
* space. This is obviously much worse than Dijkstra's algorithm, but the
* "edges" (i.e. state transitions) are much easier to code.
*
* We do not deal with long long results at all, since we make at least K
* iterations to reach a node of cost K, so we would run out of time long
* before then.
*
* The queue needed for BFS is small in practice. To keep track of visited
* elements, we use a bit set to gain as much space as possible.
**/
#include <stdio.h>
#include <stdlib.h>
#define MAX_N 45000 /* uses up to 256 MB */
#define QUEUE_SIZE 8192
#define SIGN(x, y) ((x > y) - (y > x))
typedef struct {
unsigned short l, r;
int cost;
} node;
node queue[QUEUE_SIZE];
int qstart, qend;
int alt[MAX_N];
int n;
unsigned long long bits[MAX_N][1 + MAX_N / 64];
void toggleSeen(int l, int r) {
bits[l][r >> 6] ^= 1ull << (r & 63);
}
int seen(int l, int r) {
return (bits[l][r >> 6] >> (r & 63)) & 1;
}
void dequeue(int* l, int* r, int *cost) {
*l = queue[qstart].l;
*r = queue[qstart].r;
*cost = queue[qstart].cost;
qstart = (qstart + 1) % QUEUE_SIZE;
}
void maybeEnqueue(int l, int r, int c) {
if (alt[l] == alt[r] && !seen(l, r)) {
toggleSeen(l, r);
queue[qend] = (node) { l, r, c };
qend = (qend + 1) % QUEUE_SIZE;
}
}
int bfs() {
/* start from (1, n - 2) and forbid going back to (0, n - 1) to avoid */
/* range checking */
toggleSeen(0, n - 1);
int l = 1, r = n - 2, cost = 1;
while (l != r) {
maybeEnqueue(l + 1, r - 1, cost + 1);
maybeEnqueue(l + 1, r + 1, cost + 1);
maybeEnqueue(l - 1, r - 1, cost + 1);
maybeEnqueue(l - 1, r + 1, cost + 1);
dequeue(&l, &r, &cost);
}
return cost;
}
int main() {
/* read raw altitudes and prepair step array */
int rawN, prev, h;
scanf("%d%d", &rawN, &prev);
while (--rawN) {
scanf("%d", &h);
int step = SIGN(h, prev);
for (int i = prev; i != h; i += step) {
if (n == MAX_N) {
printf("Step array exceeds maximum size of %d.\n", MAX_N);
exit(1);
}
alt[n++] = i;
}
prev = h;
}
alt[n++] = 0;
int answer = bfs();
printf("%d\n", answer);
}
Compilation message
climbers.cpp: In function 'void maybeEnqueue(int, int, int)':
climbers.cpp:63:28: warning: narrowing conversion of 'l' from 'int' to 'short unsigned int' [-Wnarrowing]
63 | queue[qend] = (node) { l, r, c };
| ^
climbers.cpp:63:31: warning: narrowing conversion of 'r' from 'int' to 'short unsigned int' [-Wnarrowing]
63 | queue[qend] = (node) { l, r, c };
| ^
climbers.cpp: In function 'int main()':
climbers.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | scanf("%d%d", &rawN, &prev);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
climbers.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | scanf("%d", &h);
| ~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
74528 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution failed because the return code was nonzero |
| 3 |
Runtime error |
0 ms |
468 KB |
Execution failed because the return code was nonzero |
| 4 |
Runtime error |
1 ms |
432 KB |
Execution failed because the return code was nonzero |
| 5 |
Runtime error |
0 ms |
468 KB |
Execution failed because the return code was nonzero |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1236 KB |
Output is correct |
| 2 |
Correct |
4 ms |
6484 KB |
Output is correct |
| 3 |
Correct |
11 ms |
18900 KB |
Output is correct |
| 4 |
Correct |
22 ms |
40404 KB |
Output is correct |
| 5 |
Correct |
12 ms |
15436 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution failed because the return code was nonzero |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution failed because the return code was nonzero |
| 3 |
Runtime error |
0 ms |
424 KB |
Execution failed because the return code was nonzero |
| 4 |
Runtime error |
1 ms |
428 KB |
Execution failed because the return code was nonzero |
| 5 |
Runtime error |
0 ms |
468 KB |
Execution failed because the return code was nonzero |
| 6 |
Runtime error |
0 ms |
468 KB |
Execution failed because the return code was nonzero |
| 7 |
Runtime error |
1 ms |
468 KB |
Execution failed because the return code was nonzero |
| 8 |
Runtime error |
0 ms |
428 KB |
Execution failed because the return code was nonzero |
| 9 |
Runtime error |
1 ms |
468 KB |
Execution failed because the return code was nonzero |
| 10 |
Runtime error |
1 ms |
468 KB |
Execution failed because the return code was nonzero |
