/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 532.0 KiB
#2 Wrong Answer 1ms 532.0 KiB
#3 Wrong Answer 2ms 360.0 KiB

Code

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// #define int long long
const int MOD = 1000000007;
#define sz(x) (ll)(x).size()
#define rd ({ll x; cin >> x; x; })
#define dbg(x) cerr << "[" #x "]  " << (x) << "\n"
// #define errv(x) {cerr << "["#x"]  ["; for (const auto& ___ : (x)) cerr << ___ << ", "; cerr << "]\n";}
// #define cerr if(0)cerr
#define xx first
#define yy second
mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
/*_________________________________________________________________________________________________________________________*/

void Solve()
{
    string s;
    cin >> s;
    ll n = sz(s);
    if (n == 1) {
        cout << s << "\n";
        return;
    }
    map<char, ll> cnt;
    for (auto c : s) {
        cnt[c]++;
    }
    for (auto& [c, v] : cnt) {
        if (v > (n + 1) / 2) {
            cout << "-1\n";
            return;
        }
    }
    vector<pair<char, ll>> arr;
    for (auto& [c, v] : cnt) {
        arr.push_back({ c, v });
    }
    string ans(n, ' ');
    ll i = 0, j = 1;
    ll iorj = 0;
    for (auto& [c, v] : arr) {
        if (!iorj) {
            for (; i < n && v; i += 2) {
                ans[i] = c;
                v--;
            }
            if (v) {
                ll last = n - 1;
                while (ans[last] != ' ')
                    last--;
                for (; last >= 0 && v; last -= 2) {
                    ans[last] = c;
                    v--;
                }
            }
        } else {
            for (; j < n && v; j += 2) {
                ans[j] = c;
                v--;
            }
            if (v) {
                ll last = n - 1;
                while (ans[last] != ' ')
                    last--;
                for (; last >= 0 && v; last -= 2) {
                    ans[last] = c;
                    v--;
                }
            }
        }
        iorj ^= 1;
    }
    while (ans.back() == ans[sz(ans) - 2]) {
        char bk = ans.back();
        ans.pop_back();
        for (int i = sz(ans) - 1; i >= 0; --i) {
            if (i == 0 || ans[i] != bk && ans[i - 1] != bk) {
                ans.insert(ans.begin() + i, bk);
                break;
            }
        }
    }
    cout << ans << "\n";
}

int32_t main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        // cout << "Case #" << i << ": "; // cout << "Case " << i << ": ";
        Solve();
    }
    return 0;
}
// Coded by Tahsin Arafat (@TahsinArafat)

Information

Submit By
Type
Submission
Problem
P1209 B. Rearrange the String
Language
C++17 (G++ 13.2.0)
Submit At
2025-07-14 18:07:07
Judged At
2025-07-14 18:07:07
Judged By
Score
0
Total Time
2ms
Peak Memory
532.0 KiB