fork download
copy 
  1. #include <vector>
  2. #include <algorithm>
  3. #include <utility>
  4. #include <iostream>
  5.  
  6. std::vector< std::pair<int, int> > get_indexes_and_values(std::vector<int> v) {
  7.    std::vector< std::pair<int, int> > ind;
  8.  
  9.     for (int i = 0; i < v.size(); i++)
  10.         ind.push_back({i, v[i]});
  11.  
  12.     return ind;
  13. }
  14.  
  15. bool second_smaller(std::pair<int, int> a, std::pair<int, int> b) {
  16.     return a.second < b.second;
  17. }
  18.  
  19. bool emerged_peak(std::vector<std::pair<int, int>> ind, std::vector<bool> visited, int i) {
  20.     if ((ind[i].first == 0 || !visited[ind[i].first - 1]) && (ind[i].first == ind.size() - 1 || !visited[ind[i].first + 1]))
  21.         return true;
  22.  
  23.     return false;
  24. }
  25.  
  26. bool flooded_peak(const std::vector<std::pair<int, int>> ind, const std::vector<bool> visited, int i) {
  27.     if (ind[i].first == 0 || ind[i].first == ind.size() - 1)
  28.         return false;
  29.  
  30.     if (visited[ind[i].first - 1] && visited[ind[i].first + 1])
  31.         return true;
  32.  
  33.     return false;
  34. }
  35.  
  36. int get_max_islands_count(const std::vector<int> v) {
  37.     int count = 0, max_count = 0;
  38.     std::vector<std::pair<int, int>> ind = get_indexes_and_values(v);    
  39.     std::vector<bool> visited(ind.size(), false);
  40.  
  41.     std::sort(ind.begin(), ind.end(), second_smaller);
  42.  
  43.     for (int i = ind.size() - 1; i > 0; i--) {
  44.         visited[ind[i].first] = true;
  45. 		std::cout << ind[i].first << " " << ind[i].second << "\n";
  46.         if (emerged_peak(ind, visited, i))
  47.             max_count = std::max(++count, max_count);
  48.         else if (flooded_peak(ind, visited, i)) 
  49.             max_count = std::max(--count, max_count);
  50.     }
  51.  
  52.     return max_count;
  53. }
  54.  
  55. int main() {
  56.     std::vector<int> v = {5, 12, 4, 10, 24, 20, 12, 18, 42, 30, 20, 35, 8};
  57.     std::cout << get_max_islands_count(v);
  58. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8 42
11 35
9 30
4 24
10 20
5 20
7 18
6 12
1 12
3 10
12 8
0 5
3
https://ideone.com/CIcVOV
language:
C++ (gcc 8.3)
created:
2 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!