59C Cofeforces - Title
Solution in c++
#include <iostream>
#include <cmath>
#include <stack>
#include <map>
using namespace std;
int fir,sz,until,errors=0,alpha_s,alp_s;
string str;
map<char,int> alpha;
int main()
{
cin>>fir>>str;
sz=str.size();
until=ceil(double(sz/2.0));
alp_s=fir;
alpha_s=0;
for(int i=0;i<fir;i++)alpha[char('a'+i)]=1;
for(int i=0;i<until;i++){
if(str[i]=='?' ^ str[sz-1-i]=='?')
{
char ideal=str[((str[sz-1-i]=='?')?i:sz-1-i)];
str[((str[i]=='?')?i:sz-1-i)]=ideal;
if(alpha[ideal])
{
alpha[ideal]=0;
alp_s--;
}
}
else if(str[i]!=str[sz-1-i]){
cout<<"IMPOSSIBLE\n";
return 0;
}
else if(str[i]==str[sz-1-i] && str[i]!='?'){
if(alpha[str[i]])
{
alpha[str[i]]=0;
alp_s--;
}
}
else if(str[i]==str[sz-1-i] && str[i]=='?')errors++;
}
if(errors >= alp_s){
stack<char> qu;
for(int i=('a'+fir-1);i>='a';i--){
if(alpha[char(i)]){
qu.push(char(i));
alpha_s++;
}
}
for(int i=0;i<until;i++){
if(errors>alpha_s && str[i]=='?'){
errors--;
str[i]='a';
str[sz-1-i]='a';
continue;
}
if(str[i]=='?'){
str[i]=qu.top();
str[sz-1-i]=qu.top();
qu.pop();
errors--;
}
if(errors==0)break;
}
cout<<str<<"\n";
}
else cout<<"IMPOSSIBLE\n";
return 0;
}
0 التعليقات:
إرسال تعليق