fork download
copy 
  1. #include <stdio.h>
  2. #include <assert.h>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <iostream>
  6.  
  7. #define MAXN 2000000
  8.  
  9. using namespace std;
  10.  
  11. int demolish(int N, int K, int L, int A[]) {
  12.     if (N == 0) return 0;
  13.  
  14.     for (int i = 0; i < N; i++)
  15.         if (A[i] >= K)
  16.             A[i] -= K;
  17.     std::sort(A, A+N);
  18.     vector<int> M(2*N);
  19.     for (int i = 0; i < N; i++) {
  20.         M[i] = A[i];
  21.         M[i+N] = A[i] + K;
  22.     }
  23.  
  24.     int sol = N;
  25.     int right = 0;
  26.     for (int left=0; left<N; ++left) {
  27.         while (M[right]-M[left] <= L) right++;
  28. //        printf("(%d:%d -- %d:%d)\n", left, M[left], right, M[right]);
  29.         sol = min(sol, right-left-1);
  30.     }
  31.     return sol;
  32. }
  33.  
  34.  
  35. int A[MAXN];
  36.  
  37. int main() {
  38.     FILE *fr, *fw;
  39.     int N, K, L, i;
  40.  
  41.     fr = stdin;
  42.     fw = stdout;
  43.  
  44.     assert(3 == fscanf(fr, "%d %d %d", &N, &K, &L));
  45.     for(i=0; i<N; i++)
  46.         assert(1 == fscanf(fr, "%d", &A[i]));
  47.  
  48.     fprintf(fw, "%d\n", demolish(N, K, L, A));
  49.     fclose(fr);
  50.     fclose(fw);
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
1 6 1
0
stdout
copy 
0
https://ideone.com/4HMJ29
language:
C++ (gcc 8.3)
created:
6 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!