fork(33) download
copy 
  1. //minimum adjacent swaps to make a string to its palindrome
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. bool check(string s)
  5. {
  6.     int n=s.length();
  7.     map<char,int> m;
  8.     for(auto i:s)
  9.     {
  10.         m[i]++;
  11.     }
  12.     int cnt=0;
  13.     for(auto i=m.begin();i!=m.end();i++)
  14.     {
  15.         if(i->second%2)
  16.         {
  17.             cnt++;
  18.         }
  19.     }
  20.     if(n%2&&cnt==1){return true;}
  21.     if(!(n%2)&&cnt==0){return true;}
  22.     return false;
  23. }
  24.  
  25. int main()
  26. {
  27.     string a;
  28.     while(cin>>a)
  29.     {
  30.         if(a[0]=='0')
  31.         {
  32.             break;
  33.         }
  34.         string s;s=a;
  35.         int n=s.length();
  36.         //first check if
  37.         int cnt=0;
  38.         bool ini=false;
  39.         if(n%2){ini=true;}
  40.         if(check(s))
  41.         {
  42.             for(int i=0;i<n/2;i++)
  43.             {
  44.                 bool fl=false;
  45.                 int j=0;
  46.                 for(j=n-1-i;j>i;j--)
  47.                 {
  48.  
  49.                     if(s[j]==s[i])
  50.                     {
  51.                         fl=true;
  52.                         for(int k=j;k<n-1-i;k++)
  53.                         {
  54.                             swap(s[k],s[k+1]);
  55.                             cnt++;
  56. //                            cout<<cnt<<endl<<flush;
  57.                         }
  58. //                        cout<<" "<<i<<" "<<cnt<<endl<<flush;
  59.                         break;
  60.                     }
  61.                 }
  62.                 if(!fl&&ini)
  63.                 {
  64.                     for(int k=i;k<n/2;k++)
  65.                     {
  66.                         swap(s[k],s[k+1]);
  67.                         cnt++;
  68.  
  69.                     }
  70. //                    cout<<cnt<<" "<<i<<" "<<endl<<flush;
  71.                 }
  72.             }
  73.             cout<<cnt<<endl;
  74.         }
  75.         else{
  76.             cout<<"Impossible"<<endl;
  77.         }
  78.     }
  79.  
  80. }
  81.  
Success #stdin #stdout 0s 4524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/8wF9DT
language:
C++14 (gcc 8.3)
created:
6 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!