比赛 2026.1.3 评测结果 AAAWAAWWWW
题目名称 KMP 最终得分 50
用户昵称 彭欣越 运行时间 0.791 s
代码语言 C++ 内存使用 9.69 MiB
提交时间 2026-01-03 11:27:21
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000010;
int n,a[N];
int idx,kmp[N];
char c[N];
int main () {
	freopen("kmpp.in","r",stdin);
	freopen("kmpp.out","w",stdout); 
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n;
	for (int i=1;i<=n;i++) {
		cin >> a[i];
		if (a[i]-a[i-1]>=2||(i==1&&a[i]==1)) {
			cout << "Impossible" <<endl;
			return 0;
		}
		if (i==1) {
			c[i]='a';
			continue;
		}
		if (a[i]==0) {
			if (c[1]!=c[i-1]||i-1==1) {
				c[i]=char((int)c[1]+1);
			}else{
				c[i]=char((int)c[2]+1);
			}
		}else c[i]=c[a[i]];
		//cout << c[i] <<endl;
	}
	int len=strlen(c+1);
    for (int i=2;i<=len;i++) {     
	    while (idx&&c[i]!=c[idx+1]) idx=kmp[idx];    
        if (c[idx+1]==c[i]) idx++;    
        kmp[i]=idx;
    }
    for (int i=1;i<=len;i++) {
    	if (kmp[i]!=a[i]) {
    		cout << "Impossible" <<endl;
			return 0;
		}
	}
	for (int i=1;i<=len;i++) cout << c[i];
    return 0;
}