fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. class Solution {
  8. public:
  9.     vector<int> findLocations(vector<int>& center, int d) {
  10.         sort(center.begin(), center.end());
  11.         vector<int> distances(center.size());
  12.         for (int i = 0; i < center.size(); ++i) {
  13.             distances[i] = calculateDistance(center, center[i]);
  14.         }
  15.         int right_bound = binarySearch(center, distances, d, 1);
  16.         int left_bound = binarySearch(center, distances, d, -1);
  17.  
  18. 		cout<<left_bound<<" "<<right_bound<<"\n";
  19.         vector<int> res;
  20.         for (int i = left_bound; i <= right_bound; ++i) {
  21.             res.push_back(i);
  22.         }
  23.  
  24.         return res;
  25.     }
  26.  
  27.     int binarySearch(vector<int>& center, vector<int>& distances, int d, int direction) {
  28.         int left = 0, right = center.size() - 1;
  29.         while (left <= right) {
  30.             int mid = left + (right - left) / 2;
  31.             int calculated_distance = distances[mid];
  32.  
  33.             if (direction == 1) {
  34.                 if (calculated_distance < d) {
  35.                     left = mid + 1;
  36.                 } else {
  37.                     right = mid - 1;
  38.                 }
  39.             } else if (direction == -1) {
  40.                 if (calculated_distance < d) {
  41.                     right = mid - 1;
  42.                 } else {
  43.                     left = mid + 1;
  44.                 }
  45.             }
  46.         }
  47.  
  48.         return (direction == 1) ? left : right;
  49.     }
  50.  
  51.     int calculateDistance(vector<int>& center, int mid) {
  52.         int res = 0;
  53.         for (int i : center) {
  54.             res += abs(mid - i);
  55.         }
  56.         return res;
  57.     }
  58. };
  59.  
  60. int main() {
  61.     Solution solution;
  62.     vector<int> center = {2, 6, 3, -4};
  63.     int d = 22;
  64.     vector<int> result = solution.findLocations(center, d);
  65.  
  66.     cout << "Result: ";
  67.     for (int index : result) {
  68.         cout << center[index] << " ";
  69.     }
  70.     cout << endl;
  71.  
  72.     return 0;
  73. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 4
Result: -4 2 3 6 0
https://ideone.com/wG4Bfc
language:
C++14 (gcc 8.3)
created:
13 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!