oj.uz

Submission #247249

# Submission time Handle Problem Language Result Execution time Memory
247249 2020-07-11T08:24:19 Z Nightlight Swimming competition (LMIO18_plaukimo_varzybos) C++14
0 / 100
 19 ms 23936 KB 
#include <bits/stdc++.h>
using namespace std;

int N, A, B;
int arr[1000005];
vector<int> pen[1000005];
bitset<1000001> can;
int p, cnt, pos;

bool check(int now) {
//  cout << now << "\n";
  p = 1;
  while(arr[p] - arr[1] <= now) p++;
  if(p <= A) return 0;

  can = 0;
  can[0] = 1;
  cnt = 0;
  
  pen[p].emplace_back(1);
  for(int i = A; i <= N; i++) {
    if(can[i - A]) cnt++;
    if(i > B + 1 && can[i - B - 1]) cnt--;
    while(!pen[i].empty()) {
      pos = pen[i].back();
      if(i - B <= pos && pos <= i - A) cnt--;
      can[pos] = 0; 
      pen[i].pop_back();
    }
//    cout << i << " " << cnt << "\n";
    if(cnt > 0) {
      can[i] = 1;
      if(i < N) while(arr[p] - arr[i + 1] <= now) p++;
      if(p != i) pen[p].emplace_back(i);
    }
  }
//  cout << "\n";
  pen[N + 1].clear();
  return can[N];
}

int main() {
  scanf("%d %d %d", &N, &A, &B);
  for(int i = 1; i <= N; i++) {
    scanf("%d", &arr[i]);
  }
  sort(arr + 1, arr + N + 1);
//  for(int i = 1; i <= N; i++) {
//    cout << arr[i] << " ";
//  }
//  cout << "\n";
  arr[N + 1] = 1e9;
  int l = 0, r = 1000000, ans;
  while(l <= r) {
    int mid = (l + r) >> 1;
    if(check(mid)) {
      r = mid - 1;
      ans = mid;
    }else l = mid + 1;
  }
  printf("%d\n", ans);
  cin >> N;
}
/*
8 8 8 
1
5
8
8
1
1
8
1000000
*/

Compilation message

plaukimo_varzybos.cpp: In function 'int main()':
plaukimo_varzybos.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &N, &A, &B);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plaukimo_varzybos.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &arr[i]);
     ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct
3 Incorrect 18 ms 23936 KB Output isn't correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 40.0

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