fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<vector<int>> v;
  5.  
  6.  
  7. void solve(){
  8.  
  9.    int k; cin>>k;
  10.    string str; cin>>str;
  11.    int n = str.size();
  12.  
  13.    int kk = k;
  14.    int insize = n;
  15.    vector<int> state;
  16.    while(kk > 1){
  17.         state.push_back(insize);
  18.         insize/=2;
  19.         kk--;
  20.    }
  21.  
  22.    //cout<<insize<<"\n";
  23.  
  24.    if(insize == 0 || insize == 2 || insize == 3){
  25.         cout<<"impossible"<<"\n";
  26.    }
  27.    else{
  28.         state.push_back(insize);
  29.         insize/=2;
  30.         int mega = insize;
  31.         for(int i = 0; i<insize; i++){
  32.             v.push_back({i});
  33.         }
  34.  
  35.         //reverse(state.begin(), state.end());
  36.  
  37.         while(state.size() != 0){
  38.             int x = state[state.size()-1];
  39.             //cout<<insize<<" ";
  40.             //cout<<x<<" ";
  41.             x-=2*insize ;
  42.             int asolsize = 2*insize + x;
  43.  
  44.             for(int i = 0; i<v.size(); i++){
  45.                 vector<int> temp;
  46.                 for(auto z: v[i]){
  47.                     temp.push_back(asolsize - z-1);
  48.                 }
  49.                 for(auto z: temp){
  50.                     v[i].push_back(z);
  51.                 }
  52.             }
  53.  
  54.             if(x == 1) v.push_back({insize});
  55.  
  56.             insize = asolsize;
  57.             state.pop_back();
  58.             //cout<<insize<<"\n";
  59.         }
  60.  
  61.         // for(int i = 0; i<v.size(); i++){
  62.         //     for(auto x: v[i]){
  63.         //         cout<<x<<" ";
  64.         //     }
  65.         //     cout<<"\n";
  66.         // }
  67.  
  68.         vector<pair<int, int>> L;
  69.         vector<pair<int, int>> R;
  70.  
  71.         int cng = 0;
  72.         for(int i = 0; i<v.size(); i++){
  73.             vector<int> hsh(26, 0);
  74.             for(auto x: v[i]){
  75.                 hsh[str[x]-'a']++;
  76.             }
  77.  
  78.             vector<pair<int, int>> pp;
  79.             for(int i = 0; i<26; i++){
  80.                 pp.push_back({hsh[i], i});
  81.             }
  82.             sort(pp.begin(), pp.end());
  83.             reverse(pp.begin(), pp.end());
  84.  
  85.             // for(int i = 0; i<3; i++) cout<<hsh[i]<<" ";
  86.             //     cout<<"\n";
  87.  
  88.             L.push_back({pp[0].second, pp[1].second});
  89.             R.push_back({v[i].size() - pp[0].first, v[i].size() - pp[1].first});
  90.             cng+= v[i].size() - pp[0].first;
  91.         }
  92.  
  93.         bool flag = 0;
  94.         insize = mega;
  95.        //cout<<mega<<"\n";
  96.         for(int i = 0; i<insize; i++){
  97.             if(L[i].first != L[insize - i-1].first) flag = 1;
  98.         }
  99.  
  100.         if(flag){
  101.             cout<<cng<<"\n";
  102.         }
  103.         else{
  104.             int ans = 1e9;
  105.             if(insize == 0) ans = cng;
  106.             for(int i = 0; i<insize/2; i++){
  107.                 ans = min(ans, cng - R[i].first + R[i].second);
  108.             }
  109.  
  110.             for(int i = (insize+1)/2; i<insize; i++){
  111.                 ans = min(ans, cng - R[i].first + R[i].second);
  112.             }
  113.  
  114.             cout<<ans<<"\n"; 
  115.  
  116.  
  117.  
  118.         }
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.    }
  126.  
  127.  
  128. }
  129.  
  130. signed main(){
  131.     // ios_base::sync_with_stdio(false);
  132.     // cin.tie(NULL);
  133.     // cout.tie(NULL);
  134.  
  135.     int t=1; //cin>>t;
  136.     //cout<<t<<"\n";
  137.     while(t--) solve();
  138.     return 0;
  139. }
  140.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
1
aca
stdout
copy 
impossible
https://ideone.com/aM0Otp
language:
C++14 (gcc 8.3)
created:
81 days 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!