QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#781896 | #8234. Period of a String | louhao088 | WA | 7ms | 14200kb | C++23 | 2.2kb | 2024-11-25 17:55:53 | 2024-11-25 17:55:54 |
Judging History
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();
}
}
Details
Tip: Click on the bar to expand more detailed information
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)