codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#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; }
Private
[
?
]
Run code
Submit