fork(1) download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4.  
  5. template <class It, class Less>
  6. bool almost_increasing_seq(It begin, It end, Less cmp) {
  7.   const auto lbound = std::adjacent_find(begin, end, std::not2(cmp));
  8.   if (lbound == end) {
  9.     return true; // already sorted
  10.   }
  11.   const auto rbound = lbound + 1;
  12.   if (rbound == end || (rbound + 1) == end) {
  13.     return true; // can just drop the last one
  14.   }
  15.   return std::adjacent_find(rbound, end, std::not2(cmp)) == end &&
  16.          (lbound == begin || cmp(*lbound, *(rbound + 1)) ||
  17.           cmp(*(lbound - 1), *rbound));
  18. }
  19.  
  20. bool almost_increasing_vector(const std::vector<int>& ints) {
  21.   return almost_increasing_seq(ints.begin(), ints.end(), std::less<int>());
  22. }
  23.  
  24. int main() {
  25.   std::cout << "[] => " << almost_increasing_vector({}) << "\n";
  26.   std::cout << "[0, 1] => " << almost_increasing_vector({0, 1}) << "\n";
  27.   std::cout << "[1, 0] => " << almost_increasing_vector({1, 0}) << "\n";
  28.   std::cout << "[0, 1, 2, 3] => " << almost_increasing_vector({0, 1, 2, 3}) << "\n";
  29.   std::cout << "[5, 1, 2, 3] => " << almost_increasing_vector({5, 1, 2, 3}) << "\n";
  30.   std::cout << "[1, 2, 0, 3] => " << almost_increasing_vector({1, 2, 0, 3}) << "\n";
  31.   std::cout << "[1, 5, 2, 3] => " << almost_increasing_vector({1, 5, 2, 3}) << "\n";
  32.   std::cout << "[1, 5, 0, 2] => " << almost_increasing_vector({1, 5, 0, 2}) << "\n";
  33.   std::cout << "[3, 2, 1, 0] => " << almost_increasing_vector({3, 2, 1, 0}) << "\n";
  34.   return 0;
  35. }
  36.  
Success #stdin #stdout 0s 4452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[] => 1
[0, 1] => 1
[1, 0] => 1
[0, 1, 2, 3] => 1
[5, 1, 2, 3] => 1
[1, 2, 0, 3] => 1
[1, 5, 2, 3] => 1
[1, 5, 0, 2] => 0
[3, 2, 1, 0] => 0
https://ideone.com/jeuT8j
language:
C++14 (gcc 8.3)
created:
8 years 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!