QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#781814 | #8234. Period of a String | louhao088 | WA | 61ms | 18152kb | C++23 | 2.1kb | 2024-11-25 17:36:21 | 2024-11-25 17:36:23 |
Judging History
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]]);
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: 100
Accepted
time: 2ms
memory: 9892kb
input:
4 2 abc abcd 4 bbcaa cabb acabbbb a 3 ab aab bbaaaaab 3 ab aab bbaaaaaa
output:
NO YES abbca abbc abbcabb a YES ab aba abaabaab NO
result:
ok ok (4 test cases)
Test #2:
score: 0
Accepted
time: 5ms
memory: 9796kb
input:
5 1 ccecddbdbbcbbaded 3 cd d d 1 dcedec 2 dcec cce 8 a e a c cc cccccccc c b
output:
YES eedddddccccbbbbba YES dc d d YES eeddcc YES eccd ecc NO
result:
ok ok (5 test cases)
Test #3:
score: -100
Wrong Answer
time: 61ms
memory: 18152kb
input:
100 147 ababbbaaaaaababbbbbaabaabbbbaaaababbbbababaabbbbaaabbabaaaaaabbbbaabbaaaaaababbbaabbabbaaabbbaabbbabaabbbbaabaabbaa aaaaabbbbababababbbaaaaaabaaaaabbaabaabaaababbabbabbabbaabbaaabbaabbaabaababaaabbababbbbbaabaaaaabbbbaabbbbbbaaabbbbabaababbbbb ababbabaababbbbaabbbbaaabbabaabbaaaababbbabbaaab...
output:
NO YES babbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaa ba bababababababababababababababababababababab bababababababababababababababab babababab bababababbababababb bababababbabab baba bababababababab b bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb b bbbbbbbbbbbbbb bbbbbbbbbbbbbb bbbbbbbbbbbbbbbbbbbbbbb bbbbbbbb...
result:
wrong answer Number of letters do not same (test case 47)