oj.uz

Submission #542504

# Submission time Handle Problem Language Result Execution time Memory
542504 2022-03-26T19:21:10 Z elira Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 1704 KB 
#include "elephants.h"

#define MAXN 500002

int n, l;
int elephants[MAXN];
int positions[MAXN];

void init(int N, int L, int X[])
{
  l = L;
  n = N;
  for (int i=0; i < n; i++) {
    elephants[i] = X[i];
    positions[i] = X[i];
  }
}

int update(int i, int y)
{
  int result = 0;
  int last_covered = -1;
  int current_pos = elephants[i];
  elephants[i] = y;
  bool type = y < current_pos;
  int carrying = -1;
  bool eating = false;
  for (int i = 0; i < n; i++) {
    if (type) {
      if (positions[i] > y ) {
        carrying = positions[i];
        positions[i] = y;
        y = 2000000000;
        if (carrying == current_pos) {
          carrying = -1;
        }
      } else if (carrying != -1) {
        if (positions[i] == current_pos) {
          positions[i] = carrying;
          carrying = -1;
        } else {
          carrying ^= positions[i];
          positions[i] ^= carrying;
          carrying ^= positions[i];
        }
      }
    }
    else {
      if (eating) {
        if (positions[i+1] >= y || i == n-1) {
          positions[i] = y;
          eating = false;
        } else {
          positions[i] = positions[i+1];
        }
      } else if (positions[i] == current_pos) {
        current_pos = -1;
        eating = true;
        i--;
        continue;
      }
    }

    if (last_covered < positions[i]) {
      result++;
      last_covered = positions[i] + l;
    }
  }
  return result;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 2399 ms 1040 KB Output is correct
8 Correct 3421 ms 1116 KB Output is correct
9 Correct 4877 ms 1480 KB Output is correct
10 Correct 3626 ms 1492 KB Output is correct
11 Correct 3835 ms 1488 KB Output is correct
12 Correct 8493 ms 1484 KB Output is correct
13 Correct 3727 ms 1484 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 2399 ms 1040 KB Output is correct
8 Correct 3421 ms 1116 KB Output is correct
9 Correct 4877 ms 1480 KB Output is correct
10 Correct 3626 ms 1492 KB Output is correct
11 Correct 3835 ms 1488 KB Output is correct
12 Correct 8493 ms 1484 KB Output is correct
13 Correct 3727 ms 1484 KB Output is correct
14 Correct 2237 ms 1336 KB Output is correct
15 Correct 6207 ms 1408 KB Output is correct
16 Execution timed out 9033 ms 1704 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 2399 ms 1040 KB Output is correct
8 Correct 3421 ms 1116 KB Output is correct
9 Correct 4877 ms 1480 KB Output is correct
10 Correct 3626 ms 1492 KB Output is correct
11 Correct 3835 ms 1488 KB Output is correct
12 Correct 8493 ms 1484 KB Output is correct
13 Correct 3727 ms 1484 KB Output is correct
14 Correct 2237 ms 1336 KB Output is correct
15 Correct 6207 ms 1408 KB Output is correct
16 Execution timed out 9033 ms 1704 KB Time limit exceeded
17 Halted 0 ms 0 KB -