oj.uz

Submission #160322

# Submission time Handle Problem Language Result Execution time Memory
160322 2019-10-27T02:20:42 Z model_code Climbers (RMI18_climbers) C
25 / 100
 1000 ms 380 KB 
/**
 * Method: naive simulation.
 *
 * Author: Catalin Francu
 *
 * Details: in the general case we can use Dijkstra's algoritm. When all
 * altitudes are distinct, however, then for every interesting climbers'
 * position exactly one of the climbers is in a node; the other one is in the
 * middle of a segment. Therefore, vertices in the graph have degree at most
 * 2, meaning there is a single path and we can simply follow it until the
 * climbers meet.
 **/
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 5000
#define INFINITY (1ull << 63)

int n;
int alt[MAX_N];

/* returns true if the altitudes at i, j and k are in ascending or descending order */
int sequence(int i, int j, int k) {
  return
    (i >= 0 && i < n && j >= 0 && j < n && k >= 0 && k < n) &&
    (
     (alt[i] < alt[j] && alt[j] < alt[k]) ||
     (alt[i] > alt[j] && alt[j] > alt[k])
     );
}

int differentPair(int x1, int y1, int x2, int y2) {
  return (x1 != x2) || (y1 != y2);
}

/* replaces (x1, y1) with (x2, y2) and returns the cost of moving */
int moveTo(int* x1, int* y1, int x2, int y2) {
  int result = abs(alt[*x1] - alt[x2]);
  *x1 = x2;
  *y1 = y2;
  return result;
}

long long greedy() {
  int x, y, prevx, prevy;
  long long cost;

  /* start after move 1 to avoid the special case of the two (equal) zeroes */
  if (alt[1] < alt[n - 2]) {
    x = 1;
    y = n - 2;
    prevx = 0;
    prevy = n - 1;
    cost = alt[1];
  } else {
    x = n - 2;
    y = 0;
    prevx = n - 1;
    prevy = 0;
    cost = alt[n - 2];
  }

  while (x != y && x != y - 1) {
    int curx = x, cury = y;
    if (sequence(y, x + 1, y + 1) && differentPair(prevx, prevy, x + 1, y)) {
      cost += moveTo(&x, &y, x + 1, y);
    } else if (sequence(x + 1, y, x) && differentPair(prevx, prevy, y, x)) {
      cost += moveTo(&x, &y, y, x);
    } else if (sequence(x, y + 1, x + 1) && differentPair(prevx, prevy, y + 1, x)) {
      cost += moveTo(&x, &y, y + 1, x);
    } else if (sequence(y, x - 1, y + 1) && differentPair(prevx, prevy, x - 1, y)) {
      cost += moveTo(&x, &y, x - 1, y);
    } else if (sequence(x - 1, y, x) && differentPair(prevx, prevy, y, x - 1)) {
      cost += moveTo(&x, &y, y, x - 1);
    } else {
      cost += moveTo(&x, &y, y + 1, x - 1);
    }
    prevx = curx;
    prevy = cury;
  }

  if (x == y - 1) {
    cost += moveTo(&x, &y, y, y);
  }

  return cost;
}

int main() {
  int numAlts;

  /* read altitudes, suppressing repeated values and monotonic runs */
  scanf("%d%d%d", &numAlts, &alt[0], &alt[1]);
  n = 2;
  while (numAlts-- > 2) {
    scanf("%d", &alt[n]);
    if (sequence(n - 2, n - 1, n)) {
      alt[n - 1] = alt[n];
    } else {
      n++;
    }
  }

  long long answer = greedy();

  printf("%lld\n", answer);
}

Compilation message

climbers.c: In function 'main':
climbers.c:93:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &numAlts, &alt[0], &alt[1]);
   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
climbers.c:96:5: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &alt[n]);
     ^~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 12 ms 256 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 256 KB Time limit exceeded
2 Execution timed out 1085 ms 256 KB Time limit exceeded
3 Execution timed out 1073 ms 256 KB Time limit exceeded
4 Execution timed out 1076 ms 256 KB Time limit exceeded
5 Execution timed out 1085 ms 256 KB Time limit exceeded

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 256 KB Time limit exceeded
2 Execution timed out 1070 ms 256 KB Time limit exceeded
3 Execution timed out 1080 ms 256 KB Time limit exceeded
4 Execution timed out 1079 ms 256 KB Time limit exceeded
5 Execution timed out 1080 ms 376 KB Time limit exceeded
6 Execution timed out 1074 ms 256 KB Time limit exceeded
7 Execution timed out 1064 ms 256 KB Time limit exceeded
8 Execution timed out 1073 ms 376 KB Time limit exceeded
9 Execution timed out 1077 ms 376 KB Time limit exceeded
10 Execution timed out 1075 ms 256 KB Time limit exceeded