QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#779758 | #8234. Period of a String | guodong | WA | 0ms | 7664kb | C++14 | 1.8kb | 2024-11-24 21:36:39 | 2024-11-24 21:36:39 |
Judging History
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)