QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#665467#8234. Period of a StringOIer_kzc#WA 269ms13932kbC++174.2kb2024-10-22 13:08:382024-10-22 13:08:43

Judging History

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

  • [2024-10-22 13:08:43]
  • 评测
  • 测评结果:WA
  • 用时:269ms
  • 内存:13932kb
  • [2024-10-22 13:08:38]
  • 提交

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];
            Sub X;
            X.l=0,X.r=h-1;
            int w=len[i]/len[i-1];
            if(h){
                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 ;
                while(w>=1){
                    --w;
                    X.r+=len[i-1];
                    fo(j,0,25)X.A[j]+=s[i-1][j];
                    int v=Add(X);
                    if(!v)return ;
                }
            }
            w=len[i]/len[i-1];
            X.l=0,X.r=-1;
            fo(j,0,25)X.A[j]=0;
            while(w>=1){
                --w;
                X.r+=len[i-1];
                fo(j,0,25)X.A[j]+=s[i-1][j];
                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: 0ms
memory: 10024kb

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: 1ms
memory: 10352kb

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: 269ms
memory: 13932kb

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)