154282025-02-19 15:33:30PKBVáltakozó (75 pont)cpp17Elfogadva 75/7526ms1312 KiB
#include <bits/stdc++.h>
using namespace std;

// Global feasibility check: can we rearrange the entire multiset (no extra restriction)
// into an alternating string? For a string of length n:
// - if n is even, every letter must appear at most n/2 times;
// - if n is odd, every letter must appear at most (n+1)/2 times.
bool globalFeasible(const vector<int> &cnt, int n) {
    if(n == 0) return true;
    if(n % 2 == 0) {
        for (int i = 0; i < 26; i++){
            if(cnt[i] > n/2) return false;
        }
    } else {
        int allowed = (n+1)/2;
        for (int i = 0; i < 26; i++){
            if(cnt[i] > allowed) return false;
        }
    }
    return true;
}

// Feasibility check for the remainder state when the next letter is not allowed to be 'forbid'.
// We have T letters remaining (T > 0) with frequencies in 'cnt' and want an alternating arrangement
// whose first letter is not equal to 'forbid'.
// The idea is that if T is even, then (like the global case) every letter may appear at most T/2 times.
// But if T is odd then the forbidden letter (which cannot be placed in the first position)
// is restricted to at most (T-1)/2 occurrences while any other letter may appear up to (T+1)/2 times.
// (Also, at least one letter must be available that is not 'forbid'.)
bool feasibleWithForbidden(const vector<int> &cnt, int T, char forbid) {
    if(T == 0) return true;
    int forbidIndex = forbid - 'a';
    // Must have at least one letter other than 'forbid'
    if(T - cnt[forbidIndex] <= 0) return false;
    if(T % 2 == 0) {
        // Even T: every letter's count must be <= T/2.
        for (int i = 0; i < 26; i++){
            if(cnt[i] > T/2) return false;
        }
    } else {
        // Odd T:
        // - For the forbidden letter: allowed maximum is (T-1)/2.
        // - For any other letter: allowed maximum is (T+1)/2.
        int allowedForbid = (T - 1) / 2;
        int allowedOther = (T + 1) / 2;
        for (int i = 0; i < 26; i++){
            if(i == forbidIndex) {
                if(cnt[i] > allowedForbid) return false;
            } else {
                if(cnt[i] > allowedOther) return false;
            }
        }
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = s.size();
    vector<int> cnt(26, 0);
    for (char c : s) {
        cnt[c-'a']++;
    }
    if(!globalFeasible(cnt, n)){
        cout << -1;
        return 0;
    }

    string ans;
    ans.reserve(n);
    char prev = '#'; // dummy (no letter yet)

    for (int pos = 0; pos < n; pos++){
        bool found = false;
        // Try every letter from 'a' to 'z'
        for (int l = 0; l < 26; l++){
            char c = 'a' + l;
            if(c == prev) continue;
            if(cnt[l] == 0) continue; // not available
            cnt[l]--;
            int rem = n - pos - 1;
            bool can = false;
            if(rem == 0) {
                can = true;
            } else {
                can = feasibleWithForbidden(cnt, rem, c);
            }
            if(can) {
                ans.push_back(c);
                prev = c;
                found = true;
                break;
            } else {
                cnt[l]++;
            }
        }
        if(!found){
            cout << -1;
            return 0;
        }
    }

    cout << ans;
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base75/75
1Elfogadva0/01ms500 KiB
2Elfogadva0/01ms316 KiB
3Elfogadva3/31ms316 KiB
4Elfogadva3/31ms316 KiB
5Elfogadva3/31ms392 KiB
6Elfogadva3/31ms316 KiB
7Elfogadva3/32ms468 KiB
8Elfogadva3/312ms956 KiB
9Elfogadva3/32ms832 KiB
10Elfogadva3/32ms820 KiB
11Elfogadva3/31ms556 KiB
12Elfogadva3/31ms316 KiB
13Elfogadva3/31ms316 KiB
14Elfogadva3/31ms316 KiB
15Elfogadva3/310ms1140 KiB
16Elfogadva3/310ms1004 KiB
17Elfogadva3/314ms1088 KiB
18Elfogadva3/319ms920 KiB
19Elfogadva3/39ms1012 KiB
20Elfogadva3/39ms1140 KiB
21Elfogadva3/310ms1020 KiB
22Elfogadva6/69ms956 KiB
23Elfogadva6/69ms1020 KiB
24Elfogadva6/626ms1312 KiB