[ create a new paste ] login | about

Link: http://codepad.org/ybsxToCs    [ raw code | fork ]

C++, pasted on Jul 8:
#include <bits/stdc++.h>
using namespace std;
typedef long long       ll;
typedef pair<int,int>   ii;
typedef vector<ii>      vii;
typedef vector<int>     vi;
#define INF 10000000000
#define pb push_back
#define mp make_pair

int k, n, dem[100];
string s;

void input(){
    cin >> k >> s;
    n = s.length();
    s = "0" + s;
    for(int i = 0; i < k; i++) dem[i] = 1;
    for(int i = k + 1; i <= 66; i++) dem[i] = 0;
}

char findd(){
    char u = 'a' + (k - 1);
    if(k == 26) u = 'z';
    for(char c = u; c >= 'a'; c--){
        if( dem[c - 'a'] == 1 ) {
            dem[c - 'a']--;
            return c;
        }
    }
    return 'a';
}

bool ok(){
    char u = 'a' + (k - 1);
    if(k == 26) u = 'z';
    for(char c = 'a'; c <= u; c++){
        if( dem[c - 'a'] == 1 ) return 0;
    }
    return 1;
}

bool dx(){
    int mid;
    if(n % 2 == 0 ) mid = n / 2;
    else mid = n / 2 + 1;
    for(int i = 1; i <= mid; i++){
        if( s[i] != s[n - i + 1] ) return 0;
    }
    return 1;
}

void process(){
    for(int i = 1; i <= n / 2; i++){
        if( s[i] != '?' && s[n - i + 1] != '?' && s[n - i + 1] != s[i] ) {
            cout << "IMPOSSIBLE";
            return;
        }
    }
    for(int i = 1; i <= n / 2; i++){
        if( s[i] != '?' && s[n - i + 1] != '?' ){
            dem[s[i] - 'a']--;
        }else if( s[i] != '?' && s[n - i + 1] == '?' ){
            s[n - i + 1] = s[i];
            dem[s[i] - 'a']--;
        }else if( s[n - i + 1] != '?' && s[i] == '?' ){
            s[i] = s[n - i + 1];
            dem[s[n - i + 1] - 'a']--;
        }
    }
    int mid;
    if(n % 2 == 0 ) mid = n / 2;
    else mid = n / 2 + 1;
    for(int i = mid; i >= 1; i--){
        if( s[i] == '?' && s[n - i + 1] == '?' ){
            s[i] = findd();
            s[n - i + 1] = s[i];
        }
    }
    if( ok() && dx() ){
        for(int i = 1; i <= n; i++) {
            cout << s[i];
        }
    }
    else cout << "IMPOSSIBLE";
}

int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
    #endif
    input();
    process();
    return 0;
}


Create a new paste based on this one


Comments: