oj.uz

Submission #203810

# Submission time Handle Problem Language Result Execution time Memory
203810 2020-02-22T08:46:25 Z EntityIT Sparklers (JOI17_sparklers) C++14
0 / 100
 5 ms 408 KB 
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

int n, k, t;
vector<double> x;

bool check(int s) {
  vector<double> X(n);
  for (int i = 0; i < n; ++i) X[i] = -x[i] + 2.0 * s * i;
  int l = k, r = k;
  double mn = X[k], mx = X[k];
  while (l || r ^ (n - 1) ) {
    if (!l) {
      ++r;
      if (mn > X[r]) return false;
      asMx(mx, X[r]);
    }
    else if (!(r ^ (n - 1) ) ) {
      --l;
      if (X[l] > mx) return false;
      asMn(mn, X[l]);
    }
    else {
      if (X[l - 1] <= mx) {
        --l;
        asMn(mn, X[l]);
      }
      else if (mn <= X[r + 1]) {
        ++r;
        asMx(mx, X[r]);
      }
      else return false;
    }
  }

  return true;
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  cin >> n >> k >> t; --k;
  x.assign(n, 0);
  for (auto &i : x) cin >> i, i /= t;

  int l = 0, r = (int)1e9;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid) ) r = mid;
    else l = mid + 1;
  }

  cout << l << '\n';

  return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 5 ms 408 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Incorrect 5 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 5 ms 408 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Incorrect 5 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Correct 5 ms 408 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Incorrect 5 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -