oj.uz

Submission #85404

# Submission time Handle Problem Language Result Execution time Memory
85404 2018-11-19T19:20:50 Z nikolapesic2802 Sparklers (JOI17_sparklers) C++14
0 / 100
 2 ms 376 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define eb emplace_back
#define ll long long
#define pii pair < int, int >
#define fr first
#define sc second
#define mk make_pair
#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define OK puts("ok");
#define whatis(x) cerr << #x << " = " << x << endl;
#define pause system("pause");
#define ld long double

const ll N = (int)1e5 + 7;
const int inf = (int)1e9 + 7;
int mod = (int)1e9 + 7;
int n, k, t;
int X[N];

bool make(vector < ld > x, vector < ld > y) {
  if (x[0] < y[0]) assert(0);
  int ok = 1;
  pii L, R;
  L = mk(0, 0);
  R = mk(0, 0);
  while (ok) {
    ok = 0;
    while (L.fr + 1 < sz(x) && x[L.fr + 1] >= y[R.sc]) {
      ok = 1;
      if (x[++L.fr] > x[L.sc]) L.sc = L.fr;
    }
    while (R.fr + 1 < sz(y) && y[R.fr + 1] <= x[L.sc]) {
      ok = 1;
      if (y[++R.fr] < y[R.sc]) R.sc = R.fr;
    }
  }
  return L.fr + 1 == sz(x) && R.fr + 1 == sz(y);
}

bool check(int s) {
  vector < ld > x, y;
  for (ll i = k; i >= 0; i--){
    x.pb(X[i] - (ld)2 * s * t * i);
    printf("%lf\n",x.back());
  }
  for (ll i = k; i < n; i++){
    y.pb(X[i] - (ld)2 * s * t * i);
    printf("%lf\n",y.back());
  }
  if (!make(x, y)) return 0;
  return 1;
}

int main() {
  cin >> n >> k >> t;
  k--;
  for (ll i = 0; i < n; i++) {
    cin >> X[i];
  }
  int l = 0;
  int r = 1e9;
  while (l < r) {
    ll mid = (l + r) / 2;
    if (check(mid)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  cout << l;
}

Compilation message

sparklers.cpp: In function 'bool check(int)':
sparklers.cpp:49:28: warning: format '%lf' expects argument of type 'double', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<long double> >::value_type {aka long double}' [-Wformat=]
     printf("%lf\n",x.back());
                    ~~~~~~~~^
sparklers.cpp:53:28: warning: format '%lf' expects argument of type 'double', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<long double> >::value_type {aka long double}' [-Wformat=]
     printf("%lf\n",y.back());
                    ~~~~~~~~^

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -