daily pastebin goal
42%
SHARE
TWEET

Untitled

a guest Oct 20th, 2018 70 Never
Upgrade to PRO!
ENDING IN00days00hours00mins00secs
  1. std::vector<int> IterateOverQueries(const std::vector<int>& input_array) {
  2.     std::vector<size_t> solved_first_subproblem;
  3.     std::vector<size_t> solved_second_subproblem;
  4.  
  5.     solved_first_subproblem.resize(input_array.size());
  6.     solved_second_subproblem.resize(input_array.size());
  7.  
  8.     solved_first_subproblem[input_array.size() - 1] = 1;
  9.     solved_second_subproblem[input_array.size() - 1] = 1;
  10.     for (int current_index = input_array.size() - 2; current_index >= 0;
  11.          --current_index) {
  12.         solved_first_subproblem[current_index] = 1;
  13.         solved_second_subproblem[current_index] = 1;
  14.         for (size_t previous_index = current_index + 1;
  15.              previous_index < input_array.size(); ++previous_index) {
  16.             if (input_array[previous_index] < input_array[current_index]) {
  17.                 solved_second_subproblem[current_index] =
  18.                         std::max(solved_first_subproblem[previous_index] + 1,
  19.                                  solved_second_subproblem[current_index]);
  20.             }
  21.             if (input_array[previous_index] > input_array[current_index]) {
  22.                 solved_first_subproblem[current_index] =
  23.                         std::max(solved_second_subproblem[previous_index] + 1,
  24.                                  solved_first_subproblem[current_index]);
  25.             }
  26.         }
  27.     }
  28.  
  29.     size_t answerlength_f = 0;
  30.     size_t answerlength_s = 0;
  31.     int answerind_f = 0;
  32.     int answerind_s = 0;
  33.     for (size_t i = 0; i < solved_first_subproblem.size(); ++i) {
  34.         if (answerlength_f < solved_first_subproblem[i]) {
  35.             answerind_f = i;
  36.             answerlength_f = solved_first_subproblem[i];
  37.         }
  38.     }
  39.     for (size_t i = 0; i < solved_second_subproblem.size(); ++i) {
  40.         if (answerlength_s < solved_second_subproblem[i]) {
  41.             answerind_s = i;
  42.             answerlength_s = solved_second_subproblem[i];
  43.         }
  44.     }
  45.     std::vector<int> answer;
  46.     answer.reserve(input_array.size());
  47.     bool decide, ans_f, ans_s;
  48.     ans_f = false;
  49.     ans_s = false;
  50.     size_t lenans;
  51.     decide = false;
  52.     if (answerlength_f > answerlength_s) {
  53.         ans_f = true;
  54.         lenans = answerlength_f;
  55.         answer.push_back(answerind_f);
  56.     } else if (answerlength_f < answerlength_s) {
  57.         ans_s = true;
  58.         lenans = answerlength_s;
  59.         answer.push_back(answerind_s);
  60.     } else {
  61.         decide = true;
  62.         lenans = answerlength_s;
  63.         answer.push_back(answerind_s);
  64.     }
  65.     lenans -= 1;
  66.     if (decide) {
  67.         for (size_t currind = answerind_f; currind < input_array.size();++currind) {
  68.             if (input_array[currind] > answer[0] && solved_first_subproblem[currind] == lenans) {
  69.                 answer.push_back(currind);
  70.                 ans_f = true;
  71.                 ans_s = false;
  72.                 lenans -= 1;
  73.                 break;
  74.             }
  75.             if (input_array[currind] < answer[0] && solved_second_subproblem[currind] == lenans) {
  76.                 answer.push_back(currind);
  77.                 ans_s = true;
  78.                 ans_f = false;
  79.                 lenans -= 1;
  80.                 break;
  81.             }
  82.         }
  83.     }
  84.     for (size_t currind = answer.back(); currind < input_array.size(); ++currind) {
  85.         if (answer.size() == 1) {
  86.             if (ans_f) {
  87.                 if (input_array[currind] > input_array[answer.back()] &&
  88.                     solved_second_subproblem[currind] == lenans) {
  89.                     answer.push_back(currind);
  90.                     lenans -= 1;
  91.                 }
  92.             } else if (ans_s) {
  93.                 if (input_array[currind] < input_array[answer.back()] &&
  94.                     solved_first_subproblem[currind] == lenans) {
  95.                     answer.push_back(currind);
  96.                     lenans -= 1;
  97.                 }
  98.             }
  99.         } else {
  100.             if (input_array[answer[answer.size() - 2]] >
  101.                 input_array[answer[answer.size() - 1]]) {
  102.                 if (input_array[currind] > input_array[answer.back()] &&
  103.                     solved_second_subproblem[currind] == lenans) {
  104.                     answer.push_back(currind);
  105.                     lenans -= 1;
  106.                 }
  107.             } else if (input_array[answer[answer.size() - 2]] <
  108.                        input_array[answer[answer.size() - 1]]) {
  109.                 if (input_array[currind] < input_array[answer.back()] &&
  110.                     solved_first_subproblem[currind] == lenans) {
  111.                     answer.push_back(currind);
  112.                     lenans -= 1;
  113.                 }
  114.             }
  115.         }
  116.     }
  117.     for (auto& x: answer) {
  118.         x = input_array[x];
  119.     }
  120.     return answer;
  121. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top