oj.uz

Submission #410602

# Submission time Handle Problem Language Result Execution time Memory
410602 2021-05-23T06:57:51 Z 600Mihnea Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 3040 KB 
#include <bits/stdc++.h>
#include "elephants.h"

using namespace std;

const int N = 150000 + 7;
int n, x[N], len, normal_ord[N];

int ind;

void init(int nn, int lenlen, int initial[]) {
  n = nn;
  len = lenlen;
  for (int i = 0; i < n; i++) {
    x[i] = normal_ord[i] = initial[i];
  }
  return;
}


void print(int v[]) {
  cout << " ----> ";
  for (int i = 0; i < n; i++) {
    cout << v[i] << " ";
  }
  cout << "\n";
}

int update(int ii, int yy) {
  {
    int value = normal_ord[ii];
    normal_ord[ii] = yy;
    int l = 0, r = n - 1, sol = -1;
    while (l <= r) {
      int m = (l + r) / 2;
      if (x[m] == value) {
        sol = m;
        break;
      }
      if (x[m] < value) {
        l = m + 1;
      } else {
        r = m - 1;
      }
    }
    assert(sol != -1);
    ii = sol;
  }
  x[ii] = yy;
  bool bad_lft = (ii - 1 >= 0 && x[ii - 1] > x[ii]);
  bool bad_rgh = (ii + 1 < n && x[ii + 1] < x[ii]);
  assert(!(bad_lft && bad_rgh));
  if (bad_lft) {
    while (ii - 1 >= 0 && x[ii - 1] > x[ii]) {
      swap(x[ii - 1], x[ii]);
      ii--;
    }
  }
  if (bad_rgh) {
    while (ii + 1 < n && x[ii + 1] < x[ii]) {
      swap(x[ii + 1], x[ii]);
      ii++;
    }
  }
  int cost = 0, l = 0;
  while (l < n) {
    cost++;
    int r = l;
    while (r + 1 < n && x[r + 1] - x[l] <= len) {
      r++;
    }
    l = r + 1;
  }

  return cost;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2866 ms 1048 KB Output is correct
8 Correct 4045 ms 2116 KB Output is correct
9 Correct 3359 ms 3040 KB Output is correct
10 Execution timed out 9056 ms 2756 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2866 ms 1048 KB Output is correct
8 Correct 4045 ms 2116 KB Output is correct
9 Correct 3359 ms 3040 KB Output is correct
10 Execution timed out 9056 ms 2756 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2866 ms 1048 KB Output is correct
8 Correct 4045 ms 2116 KB Output is correct
9 Correct 3359 ms 3040 KB Output is correct
10 Execution timed out 9056 ms 2756 KB Time limit exceeded
11 Halted 0 ms 0 KB -