【題解】Google Kick Start Round E 2021 – Shuffled Anagrams

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int t, l, cnt[26];
string s;
vector <int> v;

bool cmp(int x, int y){
    return s[x] < s[y];
}

int main(){
    cin >> t;
    for (int Case = 1; Case <= t; Case++){
        cout << "Case #" << Case << ": ";
        cin >> s;
        l = (int)s.size();
        v.clear();
        for (int i = 0; i < 26; i++) cnt[i] = 0;
        for (int i = 0; i < l; i++){
            cnt[s[i]-'a']++;
            v.push_back(i);
        }
        sort(v.begin(), v.end(), cmp);
        bool flag = true;
        for (int i = 0; i < 26; i++){
            if (cnt[i] > l-cnt[i]){
                flag = false;
                cout << "IMPOSSIBLE\n";
            }
        }
        if (!flag) continue;
        string ans = s;
        for (int i = 0; i < l; i++){
            ans[v[i]] = s[v[(i+l/2)%l]];
        }
        cout << ans << "\n";
    }
}