oj.uz

Submission #160324

# Submission time Handle Problem Language Result Execution time Memory
160324 2019-10-27T02:21:33 Z model_code Climbers (RMI18_climbers) C
30 / 100
 95 ms 74620 KB 
/**
 * 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.c: In function 'main':
climbers.c:88:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &rawN, &prev);
   ^~~~~~~~~~~~~~~~~~~~~~~~~~~
climbers.c:90:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &h);
     ^~~~~~~~~~~~~~~

Subtask #1
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 74620 KB Output is correct
2 Runtime error 2 ms 504 KB Execution failed because the return code was nonzero
3 Runtime error 2 ms 504 KB Execution failed because the return code was nonzero
4 Runtime error 2 ms 504 KB Execution failed because the return code was nonzero
5 Runtime error 2 ms 504 KB Execution failed because the return code was nonzero

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 11 ms 6628 KB Output is correct
3 Correct 27 ms 20472 KB Output is correct
4 Correct 51 ms 40428 KB Output is correct
5 Correct 22 ms 15096 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 504 KB Execution failed because the return code was nonzero
2 Runtime error 2 ms 504 KB Execution failed because the return code was nonzero
3 Runtime error 2 ms 632 KB Execution failed because the return code was nonzero
4 Runtime error 2 ms 504 KB Execution failed because the return code was nonzero
5 Runtime error 2 ms 504 KB Execution failed because the return code was nonzero
6 Runtime error 2 ms 504 KB Execution failed because the return code was nonzero
7 Runtime error 2 ms 504 KB Execution failed because the return code was nonzero
8 Runtime error 2 ms 504 KB Execution failed because the return code was nonzero
9 Runtime error 2 ms 504 KB Execution failed because the return code was nonzero
10 Runtime error 2 ms 508 KB Execution failed because the return code was nonzero