C易位构词（华师网络赛）（错排）

Time limit per test: 2.0 seconds

Memory limit: 256 megabytes

易位构词 (anagram)，指将一个单词中的字母重新排列，原单词中的每个字母都出现有且仅有一次。例如 "unce" 可以被易位构词成 "ecnu"。在某些情况下，要求重排而成的依然是一个单词，但本题没有这种要求，因为我们根本没有词典。

我们所感兴趣的是，有些单词中的字母进行适当的重排后，可以使得构成的单词每个对应的位置上字母都不一样。例如 "unce" 和 "ecnu"，就有 "u" ≠ "e", "n" ≠ "c", "c" ≠ "n", "e" ≠ "u"。现在给出一个单词，问是否存在这样一个重排。

Input

一行一个单词 s (1≤|s|≤105)。单词完全由 26 个小写英文字母构成。

Output

输出一个单词。如果有多解，输出任意解。如果不存在，输出 impossible。

Examples

input

unce

output

ecnu

input

aaaaaa

output

impossible

题意：

对于一个字符串，如果存在错排，输出它的一个错排。

思路：

如果当前的最多的字符次数Max>len/2，没有错排。如果有，输出时要维护当前Max>当前len/2，所以每次优先输出个数最多的那一个。下面是LZh的代码。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<ctime>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

int read(){

    int xx=,ff=;char ch=getchar();

    while(ch>''||ch<''){if(ch=='-')ff=-;ch=getchar();}

    while(ch>=''&&ch<=''){xx=(xx<<)+(xx<<)+ch-'';ch=getchar();}

    return xx*ff;

}

struct charar{

    int occ;

    int id;

}C[];

bool mycmp1(const charar&A,const charar&B)

{return A.occ>B.occ;}

bool mycmp2(const charar&A,const charar&B)

{return A.id<B.id;}

int len;

char s[],ans[];

int have;

int main(){

    gets(s);

    len=strlen(s);

    for(int i=;i<len;i++)

        C[s[i]-'a'].occ++;

    for(int i=;i<;i++)

        C[i].id=i;

    sort(C,C+,mycmp1);

    if(C[].occ>len/){

        printf("impossible\n");

        return ;

    }

    have=;

    for(int i=;i<=;i++){

        if(!C[i].occ)

            break;

        for(int j=;j<len;j++)

            if(C[i].id+'a'==s[j]){

                ans[j]=C[have].id+'a';

                C[have].occ--;

                if(!C[have].occ)

                    have++;

            }

    }

    for(int j=;j<len;j++)

        if(C[].id+'a'==s[j]){

            ans[j]=C[have].id+'a';

            C[have].occ--;

            if(!C[have].occ)

                have++;

        }

    for(int i=;i<len;i++)

        printf("%c",ans[i]);

    return ;

}