algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.cpp (1889B)


      1 #include <vector>
      2 #include <unordered_set>
      3 #include <iostream>
      4 #include <algorithm>
      5 
      6 void rotateLargest(std::vector<char>& chars) {
      7 
      8     char largest = 'a';
      9 
     10     std::vector<char> result {};
     11     std::vector<int> resultIndex {};
     12 
     13 
     14     for(int i = chars.size()-1; i >= 0; --i) {
     15         if(chars[i] >= largest) {
     16             largest = chars[i];
     17             result.push_back(largest);
     18             resultIndex.push_back(i);
     19         }
     20     }
     21 
     22     std::reverse(result.begin(), result.end());
     23     std::reverse(resultIndex.begin(), resultIndex.end());
     24 
     25     for(int i = 0; i < resultIndex.size(); ++i) {
     26         int nextIdx = resultIndex[(i+1) % resultIndex.size()];
     27         chars[nextIdx] = result[i];
     28     }
     29 
     30     return;
     31 }
     32 
     33 bool isSorted(std::vector<char>& st) {
     34     for(int i = 1; i < st.size(); ++i) {
     35         if(st[i] < st[i-1]) {
     36             return false;
     37         }
     38     }
     39     return true;
     40 }
     41 
     42 std::string asString(std::vector<char>& chars) {
     43     std::string result = "";
     44     for(auto& ch : chars) {
     45         result += ch;
     46     }
     47     return result;
     48 }
     49 
     50 long long solve(std::vector<char>& chars) {
     51 
     52     std::unordered_set<std::string> seen {};
     53     seen.insert(asString(chars));
     54     long long rotations = 0;
     55 
     56     while(!isSorted(chars)) {
     57         rotateLargest(chars);
     58         rotations += 1;
     59 
     60         std::string current = asString(chars);
     61 
     62         if(seen.contains(current)) {
     63             rotations = -1;
     64             break;
     65         }
     66         seen.insert(current);
     67     }
     68 
     69     return rotations;
     70 }
     71 
     72 int main() {
     73     int testCases;
     74     std::string current;
     75 
     76     std::cin >> testCases;
     77     for(int i = 0; i < testCases; ++i) {
     78         std::vector<char> chars {};
     79 
     80         std::cin >> current;
     81         current = "";
     82 
     83         std::cin >> current;
     84 
     85         for(int x = 0; x < current.size(); ++x) {
     86             chars.push_back(current[x]);
     87         }
     88 
     89         std::cout << solve(chars) << std::endl;
     90     }
     91 }