QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#779758#8234. Period of a StringguodongWA 0ms7664kbC++141.8kb2024-11-24 21:36:392024-11-24 21:36:39

Judging History

你现在查看的是最新测评结果

  • [2024-11-24 21:36:39]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7664kb
  • [2024-11-24 21:36:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=5e6+5;
int len[N],ch[35],s[N][35];
int b[N],ans[M][35];
char anss[M];
int q[N];
int main(){
	int t,n;
	cin>>t;
	while(t--){
		string st;
		cin>>n;
		for(int i=1; i<=n; i++){
			cin>>st;
			len[i]=st.length();
			for(int j=0; j<26; j++)s[i][j]=0;
			for(int j=0; j<len[i]; j++)s[i][st[j]-'a']++;
		}
		for(int i=0; i<=len[1]; i++)b[i]=0;
		int tail=1;
		q[1]=1;
		int flag=1;
		for(int i=2; i<=n; i++){
			while(tail>0&&len[i]<=len[q[tail]])tail--;
			q[++tail]=i;
			int now=len[i];
			for(int j=0; j<26; j++)ch[j]=s[i][j];
			while(now>=len[q[1]]){
				int l=1,r=tail;
				while(l<r){
					int mid=(l+r+1)/2;
					if(len[q[mid]]<now)l=mid;
					else r=mid-1;
				}
				int x=now/len[q[l]];
				for(int j=0; j<26; j++){
					ch[j]=ch[j]-x*s[q[l]][j];
					if(ch[j]<0){
						flag=0;
						break;
					}
				}
				now%=len[q[l]];
			}
			if(!b[now]){
				b[now]=1;
				for(int j=0; j<26; j++)ans[now][j]=ch[j];
			}else{
				for(int j=0; j<26; j++)
					if(ans[now][j]!=ch[j]){
						flag=0;
						break;
					}
			}
		}
		int now=0;
		for(int i=0; i<26; i++)ch[i]=0;
		for(int i=1; i<=len[1]; i++){
			if(!b[i])continue;
			for(int j=0; j<26; j++){
				if(ans[i][j]<ch[j]){
					flag=0;
					break;
				}
				for(ch[j]; ch[j]<ans[i][j]; ch[j]++)anss[now++]='a'+j;
			}
		}
		for(int j=0; j<26; j++){
			if(s[1][j]<ch[j]){
				flag=0;
				break;
			}
			for(ch[j]; ch[j]<s[1][j]; ch[j]++)anss[now++]='a'+j;
		}
		if(flag==0){
			puts("NO");
		}else{
			puts("YES");
			for(int i=0; i<now; i++)cout<<anss[i];
			cout<<endl;
			for(int i=2; i<=n; i++){
				for(int j=0; j<len[i]; j++){
					cout<<anss[j%now];
					anss[j]=anss[j%now];
				}
				cout<<endl;
				now=len[i];
			}
		}
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7664kb

input:

4
2
abc
abcd
4
bbcaa
cabb
acabbbb
a
3
ab
aab
bbaaaaab
3
ab
aab
bbaaaaaa

output:

NO
YES
abbac
abba
abbaabb
a
YES
ab
aba
abaabaab
NO

result:

wrong answer Number of letters do not same (test case 2)