fork download
copy 
  1. #pragma GCC optimize("O3")
  2. #pragma GCC target ("sse4")
  3. #include<bits/stdc++.h>
  4. #include <random>
  5. #include<ext/pb_ds/assoc_container.hpp>
  6. #include<ext/pb_ds/tree_policy.hpp>
  7.  
  8. using namespace std;
  9. using namespace chrono;
  10. using namespace __gnu_pbds;
  11.  
  12. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
  13. typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key less_equal
  14.  
  15. #ifndef ONLINE_JUDGE
  16. #define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
  17. #else
  18. #define debug(x)
  19. #endif
  20.  
  21. typedef long long ll;
  22. typedef unsigned long long ull;
  23. typedef long double lld;
  24.  
  25. void _print(ll t) {cerr << t;}
  26. void _print(int t) {cerr << t;}
  27. void _print(string t) {cerr << t;}
  28. void _print(char t) {cerr << t;}
  29. void _print(lld t) {cerr << t;}
  30. void _print(double t) {cerr << t;}
  31. void _print(ull t) {cerr << t;}
  32.  
  33. template <class T, class V> void _print(pair <T, V> p);
  34. template <class T> void _print(vector <T> v);
  35. template <class T> void _print(set <T> v);
  36. template <class T, class V> void _print(map <T, V> v);
  37. template <class T> void _print(multiset <T> v);
  38. template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.first); cerr << ","; _print(p.second); cerr << "}";}
  39. template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  40. template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  41. template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  42. template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
  43. template <class T> void _print(stack <T> st) { cerr << "[ "; while (!st.empty()) { (st.empty() ? (void)0 : (_print(st.top()), cerr << " ", st.pop())); } cerr << "]"; }
  44. template <class T> void _print(priority_queue<T> pq) {cerr << "[ "; while (!pq.empty()) { _print(pq.top()); cerr << " "; pq.pop(); } cerr << "]";}
  45. template <class T> void _print(priority_queue<T, vector<T>, greater<T>> pq) {cerr << "[ "; while (!pq.empty()) { _print(pq.top()); cerr << " "; pq.pop(); } cerr << "]"; }
  46.  
  47. #define MOD 32768
  48. #define int long long
  49. #define rep(i, a, b) for (int i = a; i < b; i++)
  50. int dp[40000][17];
  51. const int mod = 1e9 + 7;
  52.  
  53. bool isPossible(vector<int>& stalls, int n, int c, int mid) {
  54.     int cows = 1;
  55.     int lastPos = stalls[0];
  56.  
  57.     for (int i = 1; i < n; i++) {
  58.         if (stalls[i] - lastPos >= mid) {
  59.             cows++;
  60.             lastPos = stalls[i];
  61.             if (cows == c) return true;
  62.         }
  63.     }
  64.     return false;
  65. }
  66.  
  67. int findLargestMinDist(vector<int>& stalls, int n, int c) {
  68.     sort(stalls.begin(), stalls.end());
  69.     int low = 1, high = stalls[n - 1] - stalls[0], ans = 0;
  70.  
  71.     while (low <= high) {
  72.         int mid = low + (high - low) / 2;
  73.         if (isPossible(stalls, n, c, mid)) {
  74.             ans = mid;
  75.             low = mid + 1;
  76.         } else {
  77.             high = mid - 1;
  78.         }
  79.     }
  80.     return ans;
  81. }
  82.  
  83. void solve()
  84. {
  85.     int n, c;
  86.     cin >> n >> c;
  87.     vector<int> stalls(n);
  88.     for (int i = 0; i < n; i++) {
  89.             cin >> stalls[i];
  90.     }
  91.     cout << findLargestMinDist(stalls, n, c) << endl;
  92. }
  93.  
  94. signed main() {
  95.     auto begin = high_resolution_clock::now();
  96.     #ifndef ONLINE_JUDGE
  97.     freopen("errorf.in","w",stderr);
  98.     #endif
  99.     ios::sync_with_stdio(false); \
  100.     cin.tie(nullptr);                  \
  101.     int t=1;
  102.     cin>>t;
  103.     while(t--){ solve(); }
  104.     auto end = high_resolution_clock::now();
  105.     auto elapsed = duration_cast<nanoseconds>(end - begin);
  106.     cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
  107.     return 0;
  108. }
Success #stdin #stdout #stderr 0s 5284KB
comments (?)
stdin
copy 
1
5 3
1
2
8
4
9
stdout
copy 
3
stderr
copy 
Time measured: 7.735e-05 seconds.
https://ideone.com/M0zVfR
problem AGGRCOW, by mazinsk
language:
C++14 (gcc 8.3)
created:
5 days 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!