fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define all(v) v.begin(), v.end()
  5. #define sz(v) int(v.size())
  6.  
  7. using namespace std;
  8.  
  9. class EllysRain
  10. {
  11. public:
  12.  
  13. 	std::vector<int> v;
  14.  
  15. 	int get_next(int P_prev, int M, int A, int L){
  16. 		return (P_prev * M + A) % (L + 1);
  17. 	}
  18.  
  19. 	bool check(int K, int D, int L){
  20. 		std::vector<int> wow(v.begin(), v.begin()+K);
  21. 		sort(all(wow));
  22.  
  23. 		if(wow.front() > D or wow.back() < L-D)
  24. 			return 0;
  25.  
  26. 		for (int i = 0; i+1 < sz(wow); ++i)
  27. 		{
  28. 			if(wow[i+1]-wow[i] > D)
  29. 				return 0;
  30. 		}
  31.  
  32. 		return 1;
  33. 	}
  34.  
  35. 	int getTime(int L, int D, int N, int P1, int M, int A){
  36. 		for (int i = 1; i <= N; ++i)
  37. 		{
  38. 			v.pb(P1);
  39. 			P1 = get_next(P1, M, A, L);
  40. 		}
  41.  
  42. 		int low = 1, high = N, best = -1;
  43.  
  44. 		while(low <= high){
  45. 			int mid = (low + high) >> 1;
  46. 			if(check(mid, D, L)){
  47. 				high = mid-1;
  48. 				best = mid;
  49. 			}
  50. 			else{
  51. 				low = mid + 1;
  52. 			}
  53. 		}
  54. 		return best;
  55. 	}
  56.  
  57. };
  58.  
  59. int main(){
  60. 	int l, d, n, p1, m, a;
  61. 	cin >> l >> d >> n >> p1 >> m >> a;
  62. 	EllysRain x;
  63. 	cout<< x.getTime(l, d, n, p1, m, a);
  64. 	return 0;
  65. }
  66.  
Success #stdin #stdout 0s 4372KB
comments (?)
stdin
copy 
23
7
12
14
13
5
stdout
copy 
9
https://ideone.com/bfhGNa
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!