QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#710060#8234. Period of a StringnowedTL 498ms18520kbC++232.6kb2024-11-04 18:19:552024-11-04 18:19:57

Judging History

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

  • [2024-11-04 18:19:57]
  • 评测
  • 测评结果:TL
  • 用时:498ms
  • 内存:18520kb
  • [2024-11-04 18:19:55]
  • 提交

answer

#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#define endl '\n'
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;
const int N = 1e5 + 5, M = 5e6 + 5;
struct node {
    int len;
    int c[26];
} a[N], re[N];
map<int, node> f;
char ans[M];

void solve() {
    bool flag = 1;
    int n;
    f.clear();
    memset(a, 0, sizeof(a));

    cin >> n;
    rep(i, 1, n) {
        string s;
        cin >> s;
        int len = s.size();
        a[i].len = len;
        rep(j, 0, len - 1) a[i].c[s[j] - 'a']++;
    }
    int last = 0;

    auto check = [&](node A, node B) {
        rep(i, 0, 25) if (A.c[i] < B.c[i]) {
            flag = 0;
            return;
        }
        return;
    };

    for (int i = n; i >= 1; i--) {
        if (a[i].len > last) f[a[i].len] = a[i];
        else {
            int cnt = 0;
            for (auto it = --f.end();; it = --f.end()) {
                if (it->second.len <= a[i].len) break;
                node now;
                now.len = it->second.len % a[i].len;
                int x = it->second.len / a[i].len;
                rep(j, 0, 25) {
                    now.c[j] = it->second.c[j] - a[i].c[j] * x;
                    if (now.c[j] < 0) flag = 0;
                }
                if (!flag) break;
                re[++cnt] = now;
                if (it == f.begin()) {
                    f.erase(it);
                    break;
                } else f.erase(it);
            }
            if (!flag) break;
            re[++cnt] = a[i];
            rep(i, 1, cnt) if (f.find(re[i].len) == f.end()) f[re[i].len] = re[i];
            else check(f[re[i].len], re[i]); }
        last = a[i].len;
    }
    node now;
    now.len = 0;
    rep(i, 0, 25) now.c[i] = 0;
    int k = 0;

    for (auto it = f.begin(); it != f.end(); it++) {
        check(it->second, now);
        if (!flag) break;
        rep(j, 0, 25) rep(s, now.c[j] + 1, it->second.c[j]) ans[++k] = j + 'a';
        now = it->second;
    }

    if (!flag) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;

    {
        rep(i, 1, k) cout << ans[i];
        cout << endl;
        rep(i, 2, n) {
            int len = k;
            rep(j, len + 1, a[i].len) ans[j] = ans[(j - 1) % len + 1];
            rep(j, 1, a[i].len) cout << ans[j];
            cout << endl;
            k = a[i].len;
        }
    }
}

int main() {
    // ios::sync_with_stdio(0); cin.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 16208kb

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: 18152kb

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: 0
Accepted
time: 148ms
memory: 17272kb

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:

ok ok (100 test cases)

Test #4:

score: 0
Accepted
time: 145ms
memory: 16776kb

input:

100
326
decadadcaaacaaeecaddaeadeadc
aaadedcaaeaaeddddaeaceaddaaaaecccaaeadeaaedaccdddcdddaaaadddacceaaadcadaeeeadeeadccdaacadaaecaedadcaaaecdaddaeaaaeccdedaceaaaacdddcecdcdacddccecaaaeaeedacaeaadaaacdadedae
acaecaaaedcdaceaaddddaaeaddccdaeaadaeedaecdacaadeeaadeceadacdadaccdaaedaddccaceea
ddccacdcea...

output:

NO
YES
ebccdeabb
ebccde
ebccd
ebccdebccdebccdebccd
ebccde
e
eeeeeeeeeeeeeeeee
eeeeeeeeeeee
eeeeeee
eeeeeeeeeeeee
eee
eeeeeeeeeeeeeeee
eeeeeeeeeeeeee
eeeeeeeeeeeeeeeeeeee
eeeeeeeeeee
eeeeeeeeeeeeeeeeeeeee
eeeeeeeeeeeeeeeeeee
eeeeeeeeeeee
eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee
eeeeeeeeee
eee...

result:

ok ok (100 test cases)

Test #5:

score: 0
Accepted
time: 144ms
memory: 17868kb

input:

100
1114
mmiceajjcjdemdhf
c
ccccccc
cccccc
cccccccccccccccccccccccccccccccccccccccc
ccccccccc
ccccccccc
ccccccccccccccc
ccccccccccccccccccccccccc
cccccccccc
ccc
ccccccccccc
ccccccccccccccccccccccccccccccc
ccccccccc
cccccc
ccccccccccccccccccccccc
ccccccccccccc
ccc
ccccccccccc
ccccccccc
cccccccccccccc...

output:

NO
NO
YES
acgbacmikmfaaddehiibfjkacaaaaaabbbbbbcccccccccdddddeeeeeeeeeeeeefffffffgggggggghhhhhhiiiiiiiiijjjjjjjjkkkkkkklllllllmmmmm
acgbacmikmfaaddehiibfjkac
acgbacmikmfaaddehiibfjkacacgbacmikmfaaddehiibfjkacacgbacmikmfaaddehiibfjkacacgbacm
acgbacmikmfaaddehiibfjkacacgbacmikmfaaddehiibfjkacacgbacmik...

result:

ok ok (100 test cases)

Test #6:

score: 0
Accepted
time: 143ms
memory: 17400kb

input:

100
512
tecvaycvrbprboqldxlzjmlbfxaseuomtjxenfyoxkmjqkifjpacqytpxmbxleryljfxeoghwfhcnhvimgkvdwjcwatlppmwbbygdbiyzvlrfqjmdnuioulrgmwfkutwgavesanvdzbypveznnvrddujscaekxauxwi
nqmlelkfqrvjbwdlvtbzxkd
kbdqfbqxqqvmkllqltebqmlrnxvxflkzedrmbwknzltfbllqllbwllwqrvkzmrdqlldvnfbkqxbdkewxrzbbndvfqrnfklllxxkvqkjf...

output:

YES
vzxjrblkeqmvnftqbdkdllwaaaaaaaabbbbbbccccccdddddeeeeeeeffffffggggghhhiiiiijjjjjjjkkklllllmmmmmmmnnnnnoooooppppppqqrrrrrsssttttuuuuuuvvvvvvvwwwwwwxxxxxxxxyyyyyyyzzz
vzxjrblkeqmvnftqbdkdllw
vzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftqbdkdllwvzxjrblkeqmvnftq...

result:

ok ok (100 test cases)

Test #7:

score: 0
Accepted
time: 498ms
memory: 18520kb

input:

1000
379
hdiyyp
ihy
hyhyiih
hiyh
iyhhihihhyhy
yhihhyyihhih
h
hhh
h
h
hhhhh
hhhh
hhhhhhhhh
hhhhhhhhhhhhh
hhhhhhhhhhhhhhhhh
hh
hhh
hhhhh
hhhhhhhh
hhhhhhhhhhhhhhhh
hhh
hhhhhhhh
hhhhhhhhh
h
hhh
hhhhhh
hhhh
hh
hhhhhhhhhh
hhhhhhh
hh
hhhhh
hhhhhh
hhhh
h
hh
hh
hh
hh
hhhhhhhhhhhhh
hhhhh
hhhh
hhhhhh
hhhh
h
hh...

output:

YES
hiydpy
hiy
hiyhiyh
hiyh
hiyhhiyhhiyh
hiyhhiyhhiyh
h
hhh
h
h
hhhhh
hhhh
hhhhhhhhh
hhhhhhhhhhhhh
hhhhhhhhhhhhhhhhh
hh
hhh
hhhhh
hhhhhhhh
hhhhhhhhhhhhhhhh
hhh
hhhhhhhh
hhhhhhhhh
h
hhh
hhhhhh
hhhh
hh
hhhhhhhhhh
hhhhhhh
hh
hhhhh
hhhhhh
hhhh
h
hh
hh
hh
hh
hhhhhhhhhhhhh
hhhhh
hhhh
hhhhhh
hhhh
h
hhhhhh
...

result:

ok ok (1000 test cases)

Test #8:

score: -100
Time Limit Exceeded

input:

10000
21
uiutbnjregblkwbpztgdbmahtlhe
dtulrltbnbtlbggtwmteiwzbejzdlzbtbutiapwhnurumbnutkekbjehanphbhrn
unt
tnnntktntttttnttutnuuuuuunntuuuntununutnntuttunuutttntnuntnuuntuttunnuututuntuttntnunntuntnnuuttutunuunnunuutnuuutnutnutnnntntntunnttntuuttnnuunnnnuuutntn
uttnnnntuuuutututtnttuutuuttnnnnntunnu...

output:

NO
YES
y
y
y
y
y
YES
kabhlmmszgklamrcgo
kabhlmmszgklamrcgokabhlmmszgkl
kabhlmmszgklamrcgokabhlmmszgklkabhlmmszgklamrcgokabhlmmszgklkabhlmmsz
kabhlmmszgklamrcgokabhlmmszgklkabhlmmszgklamrcgokabhlmmszgklkabhlmmszkabhlmmszgklamrcgokabhlmmszgklkabhlmmszgklamrcgokabhlmmszgklkabhlmmszkabhlmmszgklamrcgokab...

result: