QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#621050#8234. Period of a StringYzm007WA 76ms250944kbC++143.9kb2024-10-08 01:24:172024-10-08 01:24:17

Judging History

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

  • [2024-10-08 01:24:17]
  • 评测
  • 测评结果:WA
  • 用时:76ms
  • 内存:250944kb
  • [2024-10-08 01:24:17]
  • 提交

answer

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10,M=5e6+10,K=26;
char s[M],ans[M];
int t,n,c,mx,par[M],sz[N],a[N][K],lim[N],b[N][K];
vector<int>del[M],del2[M];
set<int>p,q;
int find(int x){
    return par[x]==x?x:par[x]=find(par[x]);
}
void mer(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return;
    if(x>y)swap(x,y);
    par[y]=x;
}
int getch(int i){
    int fa=find(i),lb,rb;
    if(fa==i)lb=0,rb=25;
    else lb=rb=ans[fa]-'a';
    //printf("i:%d fa:%d lb:%d rb:%d\n",i,fa,lb,rb);
    rep(j,lb,rb){
        bool ok=1;
        for(auto &v:p){
            if(!b[v][j]){
                ok=0;
                break;
            }
        }
        if(!ok)continue;
        for(auto &v:q){
            if(!a[v][j]){
                ok=0;
                break;
            }
        }
        if(ok){ 
            for(auto &v:p){
                b[v][j]--;
            }
            for(auto &v:q){
                a[v][j]--;
            }
            return j;
        }
    }
    return -1;
}
bool sol(){
    rep(i,2,n){
        int x=i-1,y=i;
        if(sz[x]==sz[y]){//前后相等,完全相同
            rep(j,0,25){
                if(a[x][j]!=a[y][j])return 0;
            }
        }
        else if(sz[x]<sz[y]){//前短后长,前串是后串的循环节
            int w=sz[y]/sz[x];
            rep(j,sz[x]+1,sz[y]){
                mer(j,j-sz[x]);
            }
            rep(j,0,25){
                if(a[y][j]<1ll*a[x][j]*w)return 0;
            }
            int r=sz[y]%sz[x];
            if(r){
                lim[++c]=r;
                p.insert(c);
                rep(j,0,25){
                    b[c][j]=a[y][j]-a[x][j]*w;
                }
                del[lim[c]].pb(c);
            }
        }
        else{//前长后短,前缀相等
            rep(j,0,25){
                if(a[x][j]<a[y][j])return 0;
            }
            lim[++c]=sz[y];
            p.insert(c);
            rep(j,0,25){
                b[c][j]=a[y][j];
            }
            del[lim[c]].pb(c);
        }
    }
    rep(i,1,mx){
        int ch=getch(i);
        if(ch==-1)return 0;
        ans[i]=ch+'a';
        //printf("i:%d ans:%c\n",i,ans[i]);
        for(auto &v:del[i]){
            p.erase(v);
        }
        for(auto &v:del2[i]){
            q.erase(v);
        }
    }
    return 1;
}
int main(){
    sci(t);
    while(t--){
        mx=c=0;
        p.clear();q.clear();
        sci(n);
        rep(i,1,n){
            memset(a[i],0,sizeof(a[i]));
            scanf("%s",s+1);
            int m=strlen(s+1);
            rep(j,1,m){
                a[i][s[j]-'a']++;
            }
            sz[i]=m;
            mx=max(mx,sz[i]);
            q.insert(i);
            del2[sz[i]].pb(i);
        }
        rep(i,1,mx)par[i]=i;
        if(!sol()){
            puts("NO");
        }
        else{
            puts("YES");
            rep(i,1,n){
                int p=sz[i]+1;
                char x=ans[p];
                ans[p]='\0';
                printf("%s\n",ans+1);
                ans[p]=x;
            }
        }
        rep(i,1,c){
            del[lim[i]].clear();
        }
        rep(i,1,n){
            del2[sz[i]].clear();
        }
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 36ms
memory: 248120kb

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: 41ms
memory: 248704kb

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: 76ms
memory: 250944kb

input:

100
147
ababbbaaaaaababbbbbaabaabbbbaaaababbbbababaabbbbaaabbabaaaaaabbbbaabbaaaaaababbbaabbabbaaabbbaabbbabaabbbbaabaabbaa
aaaaabbbbababababbbaaaaaabaaaaabbaabaabaaababbabbabbabbaabbaaabbaabbaabaababaaabbababbbbbaabaaaaabbbbaabbbbbbaaabbbbabaababbbbb
ababbabaababbbbaabbbbaaabbabaabbaaaababbbabbaaab...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
YES
a
a
aa
aaaa
aaa
a
aaaaaaaa
aaaa
aaaaaaaaaa
a
aaaaa
aa
a
aaaaaaaaaaaaaaaaa
aaaa
aa
aa
aaaa
aaaaaaaaaaaaa
aaaaa
aaaaaaaaaaaa
aaaaaa
aaaaaaaaa
aaa
a
aaaaaa
aaaaaaa
a
aa
aa
a
aaaaa
aaa
aaaaaaa
aaaaaa
aaaaa
aaa
aa
...

result:

wrong answer Jury has the answer but participant has not (test case 2)