Advertisement
Josif_tepe

Untitled

Feb 1st, 2024
642
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. #include<iostream>
  2. #include <map>
  3. #include <vector>
  4. //#include<bits/stdc++.h>
  5. using namespace std;
  6. const int INF = 1e8;
  7. void swap_characters(int S, int E, string & str) {
  8.     if(S < E) {
  9.         char c = str[S];
  10.         for(int i = S; i < E; i++) {
  11.             str[i] = str[i + 1];
  12.         }
  13.         str[E] = c;
  14.     }
  15.     else {
  16.         char c = str[S];
  17.         for(int i = S; i > E; i--) {
  18.             str[i] = str[i - 1];
  19.         }
  20.         str[E] = c;
  21.     }
  22.    
  23. }
  24. int main() {
  25.     ios_base::sync_with_stdio(false);
  26.     int n;
  27.     cin >> n;
  28.     string s;
  29.     cin >> s;
  30.    
  31.     vector<int> cnt(26, 0);
  32.    
  33.     for(int i = 0; i < n; i++) {
  34.         cnt[s[i] - 'a']++;
  35.     }
  36.     int odd = 0;
  37.     for(int i = 0; i < 26; i++) {
  38.         if(cnt[i] % 2 == 1) {
  39.             odd++;
  40.         }
  41.     }
  42.     if(odd > 1) {
  43.         cout << "GRESHKA" << endl;
  44.         return 0;
  45.     }
  46.     int res = 0;
  47.     for(int i = 0; i < n / 2; i++) {
  48.         if(s[i] != s[n - i - 1]) {
  49.             int E = INF;
  50.             int S = -INF;
  51.             for(int j = i + 1; j < n - i - 1; j++) {
  52.                 if(s[j] == s[n - i - 1]) {
  53.                     E = j;
  54.                     break;
  55.                 }
  56.             }
  57.             for(int j = n - i - 2; j > i; j--) {
  58.                 if(s[j] == s[i]) {
  59.                     S = j;
  60.                     break;
  61.                 }
  62.             }
  63.             if(E - i < n - i - 1 - S) {
  64.                
  65.                 swap_characters(E, i, s);
  66.                 res += E - i;
  67.             }
  68.             else {
  69.                 swap_characters(S, n - i - 1, s);
  70.                 res += n - i - 1 - S;
  71.             }
  72.         }
  73.     }
  74.    
  75.     cout << res << endl;
  76.     return 0;
  77. }
  78.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement