fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int getMaxServers(vector<int>& arr) {
  5.     int n = arr.size();
  6.     if (n == 0) return 0;
  7.     if (n == 1) return 1;
  8.  
  9.     // Count frequencies of each value
  10.     unordered_map<int, int> freq;
  11.     for (int val : arr) {
  12.         freq[val]++;
  13.     }
  14.  
  15.     // Get all unique values and sort them
  16.     vector<int> uniqueVals;
  17.     for (auto& p : freq) {
  18.         uniqueVals.push_back(p.first);
  19.     }
  20.     sort(uniqueVals.begin(), uniqueVals.end());
  21.  
  22.     int maxLength = 1;
  23.  
  24.     // Try all possible consecutive ranges
  25.     for (int i = 0; i < uniqueVals.size(); i++) {
  26.         for (int j = i; j < uniqueVals.size(); j++) {
  27.             // Check if range [uniqueVals[i], uniqueVals[j]] is consecutive
  28.             bool isConsecutive = true;
  29.             for (int k = i; k < j; k++) {
  30.                 if (uniqueVals[k + 1] != uniqueVals[k] + 1) {
  31.                     isConsecutive = false;
  32.                     break;
  33.                 }
  34.             }
  35.  
  36.             if (isConsecutive) {
  37.                 // For a consecutive range to form a valid circle, we need to check:
  38.                 // 1. Single value: always valid
  39.                 // 2. Two consecutive values: always valid  
  40.                 // 3. Three or more: valid only if we have enough middle values to "bridge"
  41.  
  42.                 int rangeSize = j - i + 1;
  43.                 int totalCount = 0;
  44.                 for (int k = i; k <= j; k++) {
  45.                     totalCount += freq[uniqueVals[k]];
  46.                 }
  47.  
  48.                 if (rangeSize == 1) {
  49.                     // Single value - always valid
  50.                     maxLength = max(maxLength, totalCount);
  51.                 } else if (rangeSize == 2) {
  52.                     // Two consecutive values - always valid
  53.                     maxLength = max(maxLength, totalCount);
  54.                 } else {
  55.                     // Three or more consecutive values
  56.                     // We need at least 2 middle values to bridge first and last
  57.                     int middleCount = 0;
  58.                     for (int k = i + 1; k < j; k++) {
  59.                         middleCount += freq[uniqueVals[k]];
  60.                     }
  61.  
  62.                     if (middleCount >= 2) {
  63.                         // We have enough middle elements to form a valid circle
  64.                         maxLength = max(maxLength, totalCount);
  65.                     }
  66.                 }
  67.             }
  68.         }
  69.     }
  70.  
  71.     return maxLength;
  72. }
  73.  
  74. int main() {
  75.     // vector<int> powers = {4, 3, 5, 1, 2, 2, 1};
  76.     // vector<int> powers = {3, 7, 5, 1, 5};
  77.     // vector<int> powers = {2, 2, 3, 2, 1, 2, 2};
  78.     vector<int> powers = {1,2,3,4,5};
  79.     cout << getMaxServers(powers) << endl;  // Output: 5
  80.     return 0;
  81. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
5
https://ideone.com/da8YVE
language:
C++14 (gcc 8.3)
created:
1 day 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!