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 }