Submission #674741

#	Time	Username	Problem	Language	Result	Execution time	Memory
674741		sugartheanh	Climbers (RMI18_climbers)	C++14	30 / 100	39 ms	74528 KiB

climbers

/**
 * 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 (stderr)

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);
      |     ~~~~~^~~~~~~~~~

• Subtask 1: 5 / 25
• Subtask 2: 25 / 25
• Subtask 3: 0 / 50