QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#605575#8234. Period of a StringDBsoleil#WA 2ms7304kbC++203.4kb2024-10-02 18:00:162024-10-02 18:00:21

Judging History

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

  • [2024-10-02 18:00:21]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7304kb
  • [2024-10-02 18:00:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;

const int N=1e5+5,K=26;
int T,n,len[N];
string t[N];

struct req
{
    int x[26];
    req() {for(int i=0;i<K;i++) x[i]=0;}

    int&operator [](int i) {return x[i];}

    int sum()
    {
        int res=0;
        for(int i=0;i<K;i++) res+=x[i];
        return res;
    }

    req friend operator + (req a,req b)
    {
        req res;
        for(int i=0;i<K;i++) res[i]=max(a[i],b[i]);
        return res;
    }

    req friend operator * (req a,int b)
    {
        req res;
        for(int i=0;i<K;i++) res[i]=a[i]*b;
        return res;
    }

    req friend operator -(req a,req b)
    {
        req res;
        for(int i=0;i<K;i++) res[i]=max(a[i]-b[i],0);
        return res;
    }

    bool friend operator > (req a,req b)
    {
        for(int i=0;i<K;i++) if(a[i]>b[i]) return 1;
        return 0;
    }
};

void prin(req x)
{
    for(int i=0;i<K;i++) cerr<<' '<<x[i];
    cerr<<endl;
}

vector<req> ve[N]; 

void input()
{
    string s;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>s,len[i]=s.size();
        ve[i].clear(),ve[i].resize(len[i]);
        for(int j=0;j<len[i];j++) ve[i][len[i]-1][s[j]-'a']++;
    }
}

bool work(vector<req>&u,vector<req>&v,int lu,int lv)
{
    if(lu<=lv)
    {
        for(int i=0;i<lu;i++) v[i]=v[i]+u[i];
        for(int i=0;i<lv;i++)
        {
            if(i>0) v[i]=v[i]+v[i-1];
            //cerr<<i<<endl;
            //prin(v[i]);
            if(v[i].sum()>i+1) return 0;
        }
        return 1;
    }
    req rq=v[lv-1];
    int p=(lu+lv-1)/lv;
    if(u[lu-1]>(rq*p)) return 0;
    //prin(rq),prin(rq*1);
    for(int l=0,p=0;l<lu;l+=lv,p++)
    {
        int r=min(l+lv,lu);
        if(r%lv==0&&(u[r-1]+(rq*(p+1))).sum()>r) return 0;
        for(int i=l;i<r;i++) v[i%lv]=v[i%lv]+(u[i]-(rq*p));
        //cerr<<l<<' '<<r<<endl;
        //prin(u[r-1]);
        //prin((u[r-1]+(rq*(p+1))));
    }
    //for(int i=0;i<lv;i++) prin(v[i]);
    for(int i=1;i<lv;i++) v[i]=v[i]+v[i-1];
    for(int i=0;i<lv;i++) if(v[i].sum()>i+1) return 0;
    return 1;
}

bool check()
{
    for(int i=n-1;i>=1;i--) 
    {
        //cerr<<i<<endl;
        if(!work(ve[i+1],ve[i],len[i+1],len[i])) return 0;
        //cerr<<endl;
    }
    return 1;
}

bool getans(vector<req>&u,vector<req>&v,int lu,int lv,string&su,string&sv)
{
    sv="";
    req nw;
    if(lu==-1)
    {
        for(int i=0;i<lv;i++) 
        {
            for(int j=0;j<K;j++) if(nw[j]<v[i][j])
            {
                sv+=char('a'+j);
                nw[j]++;
            }
        }
        return 1;
    }
    int p=lv/lu,q=lv%lu;
    for(int i=1;i<=p;i++) sv+=su;
    sv+=su.substr(0,q);
    //cerr<<sv<<endl;
    for(int i=0;i<lv;i++)
    {
        nw[sv[i]-'a']++;
        //prin(nw); prin(v[i]);
        if((nw+v[i]).sum()>i+1) return 0;
    }
    return 1;
}

bool output()
{
    len[0]=-1;
    for(int i=1;i<=n;i++) 
    {
        //cerr<<i<<endl;
        if(!getans(ve[i-1],ve[i],len[i-1],len[i],t[i-1],t[i])) return 0;
        //cerr<<t[i]<<endl;
    }
    return 1;
}

void solve()
{
    input();
    if(!check()||!output()) cout<<"NO"<<endl;
    else
    {
        cout<<"YES"<<endl;
        for(int i=1;i<=n;i++) cout<<t[i]<<endl;
    }
}

int main()
{
    cin.sync_with_stdio(0),cin.tie(0);
    cin>>T;
    while(T--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 6804kb

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: -100
Wrong Answer
time: 2ms
memory: 7304kb

input:

5
1
ccecddbdbbcbbaded
3
cd
d
d
1
dcedec
2
dcec
cce
8
a
e
a
c
cc
cccccccc
c
b

output:

YES
abcde
YES
dc
d
d
YES
cde
YES
cecd
cec
NO

result:

wrong answer Wrong length of string (test case 1)