QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#781809#8234. Period of a Stringlouhao088WA 6ms10116kbC++232.1kb2024-11-25 17:35:522024-11-25 17:36:02

Judging History

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

  • [2024-11-25 17:36:02]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:10116kb
  • [2024-11-25 17:35:52]
  • 提交

answer

#pragma GCC Optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define int long long
#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];
int top,ch[M][27];
vector<int>sum[27];
vector<int>a[maxn];
char s[maxn];
void print(){
	puts("YES");
	vector<int>tmp;
	for(int j=0;j<26;j++){
		for(auto i:sum[j])tmp.pb(i*26+j);
	}
	sort(tmp.begin(),tmp.end());

	for(int i=sz[1]-1;i>=0;i--){
		s[sz[1]-i-1]=tmp[i]%26+'a';
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<sz[i];j++)
			putchar(s[a[i][j]]+1);
		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']++;
		sum[s[i]-'a'].pb(0);
		a[1][i]=i;
	}
	st[++top]=1;bool flag=0;
	//cout<<sz[1]<<endl;
	for(int i=2;i<=n;i++){
		scanf("%s",s);
		//if(T==53){cout<<s<<endl;}
		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);
		}
		for(int j=0;j<26;j++)if(tmp[j]>0){
			if(tmp[j]>ch[st[1]][j]){flag=1;break;}
			for(int k=0;k<tmp[j];k++)sum[j][k]++;
		}
		
		while(top&&sz[st[top]]>sz[i])top--;
		st[++top]=i;
	}
	
	if(flag)puts("NO");
	else print();
	for(int i=1;i<=n;i++){
		for(int j=0;j<=26;j++)ch[i][j]=0;
		a[i].clear();
	}
	for(int i=0;i<=26;i++)sum[i].clear();
	
}
signed main(){
	T=read();
	while(T--){
		solve();
	}
	
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 10116kb

input:

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

output:

NO
YES
bccdb
bccd
bccdbcc
b
YES
bc
bcb
bcbbcbbc
NO

result:

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