QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#665452 | #8234. Period of a String | OIer_kzc# | WA | 69ms | 11884kb | C++17 | 3.8kb | 2024-10-22 12:57:19 | 2024-10-22 12:57:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define p 1000000007
#define ll long long
int read(){
int u=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9'){
u=u*10+c-48;
c=getchar();
}
return u;
}
int n;
int s[100011][26],len[100011];
struct Sub{
int A[26];
int l,r;
friend bool operator <(Sub x,Sub y){
return (x.l<y.l);
}
void build(int x){
l=0,r=len[x]-1;
fo(j,0,25)A[j]=s[x][j];
}
bool Cut(Sub y){
fo(j,0,25){
if(y.A[j]>A[j])return 0;
A[j]-=y.A[j];
}
l=y.r+1;
return 1;
}
};
Sub fir;
char s2[5000011];
set<Sub>F;
string ans[100011];
bool Add(Sub X){
auto it=F.begin();
while(it!=F.end()){
if((*it).r<=X.r){
int v=X.Cut(*it);
if(!v){
puts("NO");
return 0;
}
}
else{
if(X.l<=X.r){
Sub v=(*it);
int u=v.Cut(X);
if(!u){
puts("NO");
return 0;
}
F.erase(it);
F.insert(X);
F.insert(v);
}
return 1;
}
++it;
}
if(X.l<=X.r){
F.insert(X);
}
return 1;
}
void qin(Sub x,int R){
int u=0;
fo(i,x.l,x.r){
while(x.A[u]==0)++u;
int r=R;
while(r&&len[r]>i&&ans[r][i]=='#'){
ans[r][i]='a'+u;
--r;
}
--x.A[u];
}
}
void solve(){
n=read();
fo(i,1,n){
scanf("%s",s2);
len[i]=strlen(s2);
memset(s[i],0,sizeof(s[i]));
fo(j,0,len[i]-1){
++s[i][s2[j]-'a'];
}
ans[i].clear();
fo(j,1,len[i])ans[i].push_back('#');
}
F.clear();
Sub Init;
Init.build(1);
F.insert(Init);
fo(i,2,n){
if(len[i]<=len[i-1]){
Sub X;
X.build(i);
int v=Add(X);
if(!v)return ;
auto it=F.end();
--it;
while((*it).l>=len[i]){
qin((*it),i-1);
--it;
}
++it;
while(it!=F.end()){
auto it2=it;
++it2;
F.erase(it);
it=it2;
}
}
else{
int h=len[i]%len[i-1];
if(h){
Sub X;
X.l=0,X.r=h-1;
int w=len[i]/len[i-1];
fo(j,0,25){
X.A[j]=s[i][j]-s[i-1][j]*w;
if(X.A[j]<0){
puts("NO");
return ;
}
}
int v=Add(X);
if(!v)return ;
}
Sub X;
X.build(i);
int v=Add(X);
if(!v)return ;
}
}
while(F.size()){
qin(*F.begin(),n);
F.erase(F.begin());
}
fo(i,2,n){
fo(j,0,len[i-1]-1){
int u=j;
while(u<len[i]){
ans[i][u]=ans[i-1][j];
u+=len[i-1];
}
}
}
fo(i,1,n){
int h[26]={0};
fo(j,0,len[i]-1)h[ans[i][j]-'a']++;
fo(j,0,25){
if(s[i][j]!=h[j]){
puts("NO");
return ;
}
}
}
puts("YES");
fo(i,1,n){
cout<<ans[i]<<"\n";
}
}
int main(){
int T=read();
while(T){
--T;
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 10192kb
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: 0ms
memory: 11884kb
input:
5 1 ccecddbdbbcbbaded 3 cd d d 1 dcedec 2 dcec cce 8 a e a c cc cccccccc c b
output:
YES abbbbbccccdddddee YES dc d d YES ccddee YES cced cce NO
result:
ok ok (5 test cases)
Test #3:
score: -100
Wrong Answer
time: 69ms
memory: 10576kb
input:
100 147 ababbbaaaaaababbbbbaabaabbbbaaaababbbbababaabbbbaaabbabaaaaaabbbbaabbaaaaaababbbaabbabbaaabbbaabbbabaabbbbaabaabbaa aaaaabbbbababababbbaaaaaabaaaaabbaabaabaaababbabbabbabbaabbaaabbaabbaabaababaaabbababbbbbaabaaaaabbbbaabbbbbbaaabbbbabaababbbbb ababbabaababbbbaabbbbaaabbabaabbaaaababbbabbaaab...
output:
NO YES baaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb ba bababababababababababababababababababababab bababababababababababababababab babababab bababababbababababb bababababbabab baba bababababababab b bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb b bbbbbbbbbbbbbb bbbbbbbbbbbbbb bbbbbbbbbbbbbbbbbbbbbbb bbbbbbbb...
result:
wrong answer Jury has the answer but participant has not (test case 4)