因为是字典序所以贪心选当前能选的最小的,所以问题就在于怎么快速计算当前这个位置能不能选枚举的字母
重排之后的序列是可以和原序列完美匹配的,而完美匹配需要满足hall定理,也就是左边任意k个集合一定和右边至少k个点相连
又一共6个字符,原序列中相同字符点连出的点集是一样的,所以只要2^6个字符集合满足hall定理,每次这样枚举状压判断一下即可
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100005;
int n,m,sm[N],f[N][70],ok[N];
char s[N],c[10],flg,ans[N];
int main()
{
scanf("%s%d",s+1,&m);
n=strlen(s+1);
for(int i=1;i<=n;i++)
for(int j=0;j<(1<<6);j++)
if(j&(1<<(s[i]-'a')))
sm[j]++;
for(int i=1;i<=n;i++)
ok[i]=(1<<6)-1;
for(int i=1,x;i<=m;i++)
{
scanf("%d%s",&x,c+1);
ok[x]=0;
for(int j=1;j<=strlen(c+1);j++)
ok[x]+=(1<<(c[j]-'a'));
}
for(int i=n;i>=1;i--)
for(int j=0;j<(1<<6);j++)
f[i][j]=f[i+1][j]+(((j&ok[i])==ok[i])?1:0);
for(int i=1;i<=n;i++)
{
bool fl=0;
for(int j=0;j<6&&!fl;j++)
if(sm[1<<j]&&(ok[i]&(1<<j)))
{
flg=1;
for(int k=0;k<(1<<6)&&flg;k++)
if(f[i+1][k]>sm[k]-((k>>j)&1))
flg=0;
if(flg)
{
fl=1;
ans[i]='a'+j;
for(int k=0;k<(1<<6);k++)
if(k&(1<<j))
sm[k]--;
}
}
if(!flg)
{
puts("Impossible");
return 0;
}
}
for(int i=1;i<=n;i++)
printf("%c",ans[i]);
return 0;
}