QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#709578#8234. Period of a StringnowedWA 149ms14380kbC++232.9kb2024-11-04 15:35:212024-11-04 15:35:25

Judging History

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

  • [2024-11-04 15:35:25]
  • 评测
  • 测评结果:WA
  • 用时:149ms
  • 内存:14380kb
  • [2024-11-04 15:35:21]
  • 提交

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;
struct node {
    int len;
    int c[26];
} a[N];
map<int, node> f;
vector<node> re;


void solve() {
    bool flag = 1;
    int n;
    cin >> n;
    auto init = [&]() {
        f.clear();
        memset(a, 0, sizeof(a));
    };
    init();
    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 {
            re.clear();
            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.push_back(now);
                if (it == f.begin()) {
                    f.erase(it);
                    break;
                } else f.erase(it);
            }
            if (!flag) break;
            re.push_back(a[i]);
            for (auto it = re.begin(); it != re.end(); it++)
                if (f.find(it->len) == f.end()) f[it->len] = *it;
                else check(f[it->len], *it);
        }
        last = a[i].len;
    }
    for (auto it = f.begin(); it != f.end(); it++)
        if (it != f.begin()) check(it->second, f.begin()->second);

    if (!flag) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    vector<char> ans;
    int Ans[26];
    ans.clear();
    memset(Ans, 0, sizeof(Ans));
    {
        for (auto it = f.begin(); it != f.end(); it++) rep(j, 0, 25) {
                while (Ans[j] < it->second.c[j]) {
                    ans.push_back(j + 'a');
                    Ans[j]++;
                }
            }
    }
    {
        for (auto it = ans.begin(); it != ans.end(); it++) cout << *it;
        cout << endl;
        vector<char> Last = ans;
        rep(i, 2, n) {
            ans.clear();
            int len = Last.size();
            rep(j, 1, a[i].len) ans.push_back(Last[(j - 1) % len]);
            for (auto it = ans.begin(); it != ans.end(); it++) cout << *it;
            cout << endl;
            Last = ans;
        }
    }
}

int main() {
    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: 4ms
memory: 14092kb

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: 4ms
memory: 14380kb

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: 149ms
memory: 14252kb

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

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:

wrong answer Number of letters do not same (test case 71)