QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#709498#8234. Period of a StringcarottTL 3ms13880kbC++205.5kb2024-11-04 15:03:432024-11-04 15:03:54

Judging History

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

  • [2024-11-04 15:03:54]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:13880kb
  • [2024-11-04 15:03:43]
  • 提交

answer

//Created by carottx on 2024-11-04.

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <complex>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <random>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

namespace IO {
const int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc()                                                               \
  (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
       ? EOF                                                               \
       : *p1++)

int rd() {
  int x = 0, f = 1;
  char c = gc();
  while (!isdigit(c)) {
    if (c == '-') f = -1;
    c = gc();
  }
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
  return x * f;
}

char pbuf[1 << 20], *pp = pbuf;

void push(const char &c) {
  if (pp - pbuf == 1 << 20) fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
  *pp++ = c;
}

void clear(){
    fwrite(pbuf, 1, strlen(pbuf), stdout);
    pp = pbuf;
}

void write(int x) {
  static int sta[35];
  int top = 0;
  do {
    sta[top++] = x % 10, x /= 10;
  } while (x);
  while (top) push(sta[--top] + '0');
}
}  // namespace IO

const int maxn=100005;
const int INF=1e9+7;

// using namespace MYDEBUG;

int n;
string s[maxn];
string ans[maxn];
int len[maxn];

struct Restriction{
    int len;
    int cnt[26];
    void clear(){len=0;memset(cnt, 0, sizeof(cnt));}
    Restriction operator+(char c){
        Restriction nr;
        memcpy(nr.cnt, cnt, sizeof(cnt));
        nr.cnt[c-'a']++;
        nr.len = len+1;
        return nr;
    }
    Restriction operator-(Restriction other){
        Restriction nr;
        for(int i=0; i<26; ++i) nr.cnt[i] = cnt[i] - other.cnt[i];
        nr.len = len - other.len;
        return nr;
    }
    Restriction operator*(int x){
        Restriction nr;
        nr.len = len*x;
        for(int i=0; i<26; ++i) nr.cnt[i] = x*cnt[i];
        return nr;
    }
    bool operator<(const Restriction& other)const{
        return len < other.len;
    }
    bool check(){
        for(int i=0;i<26;++i){
            if(cnt[i] < 0) return false;
        }
        return true;
    }
};

Restriction r[maxn];

void solve(){
    // cerr<<"!!!!!!!!!!!!!!!!!!!!!!!"<<endl;
    cin>>n;
    for(int i=0; i<n; ++i) r[i].clear();
    for(int i=0; i<n; ++i) cin>>s[i];
    for(int i=0; i<n; ++i) {
        len[i] = s[i].length();
        Restriction& tmp = r[i];
        tmp = tmp + s[i][0];
        for(int j=1; j<len[i]; ++j){
            tmp = tmp +s[i][j];
        }
    }
    int LenOfFirst = len[0];
    set<pii> S;
    S.insert(pii(-1,0));
    vector<Restriction> r0;
    for(int i=1; i<n; ++i){
        int NowLen = len[i];
        auto tmp = r[i];
        while(NowLen != 0){
            auto it = upper_bound(S.begin(), S.end(), pii(NowLen,1e9));
            it--;
            int ModLen = it->first;
            int id = it->second;
            if(ModLen!=-1) {
                tmp = tmp - r[id] * (NowLen/ModLen);
                NowLen %= ModLen;
            }
            else {
                tmp = tmp - r[id] * (NowLen/LenOfFirst);     
                NowLen %= LenOfFirst ;          
                break;
            }
        }
        if(NowLen){
            int mul = (len[i]-NowLen)/LenOfFirst;
            r0.push_back(tmp);
        }
        S.insert(pii(len[i],i));
    }
    sort(r0.begin(),r0.end());
    r0.push_back(r[0]);
    Restriction now;
    now.clear();
    bool flag = false;
    string& new0 = ans[0];
    new0 = "";
    for(auto& rr: r0){
        // cerr<<"----------------\n";
        // for(int i=0; i<26; ++i) {
        //     if(rr.cnt[i] >0) cerr<<char(i+'a')<<' '<<rr.cnt[i]<<endl;
        // }
        Restriction tmp = rr-now;
        for(int i=0; i<26; ++i) 
        {
            if(tmp.cnt[i] < 0){
                flag = true;
                break;
            } 
            else if(tmp.cnt[i] > 0){
                for(int k=0; k<tmp.cnt[i]; ++k) new0 += i+'a';
            }
        }
        now = rr;
    }
    for(int i=1; i<n && !flag; ++i){
        int mul = len[i]/len[i-1];
        auto delta = r[i] - r[i-1] * mul;
        if(!delta.check()) {flag=true;break;}
        ans[i] = "";
        for(int j=0; j<mul; ++j) ans[i] += ans[i-1];
        for(int j=0; j<delta.len; ++j){
            if(delta.cnt[ans[i-1][j]-'a']<=0) {flag=true;break;} 
            delta.cnt[ans[i-1][j]-'a'] --;
            ans[i] += ans[i-1][j];
        }
    }
    if(flag) {
        IO::push('N');
        IO::push('O');
        IO::push('\n');
        return;
    }
    IO::push('Y');
    IO::push('E');
    IO::push('S');
    IO::push('\n');
    for(int i=0;i<n;++i){
        for(int j=0; j<ans[i].length(); ++j) IO::push(ans[i][j]);
        IO::push('\n');
    }
}

int main(){
    // freopen("output.txt","w",stderr);
    // freopen("test.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--) solve();
    IO::clear();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 13880kb

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: 2ms
memory: 11988kb

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
Time Limit Exceeded

input:

100
147
ababbbaaaaaababbbbbaabaabbbbaaaababbbbababaabbbbaaabbabaaaaaabbbbaabbaaaaaababbbaabbabbaaabbbaabbbabaabbbbaabaabbaa
aaaaabbbbababababbbaaaaaabaaaaabbaabaabaaababbabbabbabbaabbaaabbaabbaabaababaaabbababbbbbaabaaaaabbbbaabbbbbbaaabbbbabaababbbbb
ababbabaababbbbaabbbbaaabbabaabbaaaababbbabbaaab...

output:


result: