QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#781896#8234. Period of a Stringlouhao088WA 7ms14200kbC++232.2kb2024-11-25 17:55:532024-11-25 17:55:54

Judging History

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

  • [2024-11-25 17:55:54]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:14200kb
  • [2024-11-25 17:55:53]
  • 提交

answer

#pragma GCC Optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define lowbit(i) (i&(-i))
const int mod=1e9+7,maxn=5e6+5,M=1e5+5;
inline int read(){
	char ch=getchar();int x=0;bool f=0;
	for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
	for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
	if(f==1)x=-x;return x;
}
int T,n,m,x;
int sz[maxn],st[maxn],g[maxn];
int top,ch[M][27],ans[maxn][27];
int sum[27];
vector<int>a[maxn];
char s[maxn];
void print(){
	puts("YES");
	for(int i=1;i<=n;i++){
		for(int j=0;j<sz[i];j++)
			putchar(s[a[i][j]]);
		puts("");
	}
}
int get(int x){
	int l=0,r=top,res=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(sz[st[mid]]<=x)res=mid,l=mid+1;
		else r=mid-1;
	}return st[res];
}
void solve(){
	n=read();top=0;
	scanf("%s",s);
	//if(T==53){cout<<n<<endl;cout<<s<<endl;}
	sz[1]=strlen(s);a[1].resize(sz[1]);
	for(int i=0;i<sz[1];i++){
		ch[1][s[i]-'a']++;
		a[1][i]=i;
	}
	st[++top]=1;bool flag=0;
	for(int i=2;i<=n;i++){
		scanf("%s",s);
		sz[i]=strlen(s);
		a[i].resize(sz[i]);
		vector<int>tmp;
		tmp.clear();
		tmp.resize(27);
		for(int j=0;j<sz[i];j++){
			a[i][j]=a[i-1][j%sz[i-1]];
			ch[i][s[j]-'a']++;
			tmp[s[j]-'a']++;
		}
		int t=sz[i],z=get(t);

		while(z){
			int p=t/sz[z];
			t=t%sz[z];
			for(int j=0;j<26;j++){
				tmp[j]=tmp[j]-ch[z][j]*p;
				if(tmp[j]<0){flag=1;break;}
			}z=get(t);
		}
		if(!g[t]){
			g[t]=1;
			for(int j=0;j<26;j++){
				ans[t][j]=tmp[j];
				if(tmp[j]>ch[1][j]){flag=1;break;}
			}
		}
		else {
			for(int j=0;j<26;j++)if(ans[t][j]!=tmp[j]){flag=1;break;}
		}
		while(top&&sz[st[top]]>=sz[i])top--;
		st[++top]=i;
	}
	for(int i=0;i<26;i++)sum[i]=0;
	int tot=0;
	for(int i=0;i<sz[1];i++){
		if(!g[i])continue;
		for(int j=0;j<26;j++)if(sum[j]>ans[i][j])flag=1;
		for(int j=0;j<26;j++)if(sum[j]<ans[i][j]){
			for(int k=sum[j]+1;k<=ans[i][j];k++)s[++tot]=j+'a';
			sum[j]=ans[i][j];
		}
		for(int j=0;j<26;j++)ans[i][j]=0;
	}
	if(flag)puts("NO");
	else print();
	for(int i=1;i<=n;i++){
		g[i]=0;
		for(int j=0;j<=26;j++)ch[i][j]=0;
		a[i].clear();
	}
	
}
signed main(){
	T=read();
	while(T--){
		solve();
	}
	
}

详细

Test #1:

score: 0
Wrong Answer
time: 7ms
memory: 14200kb

input:

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

output:

NO
YES
aabbc
aabb
aabbaab
a
YES
ba
bab
babbabba
NO

result:

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