QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#714429#8234. Period of a StringRhineWA 144ms37628kbC++234.9kb2024-11-05 23:10:542024-11-05 23:10:56

Judging History

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

  • [2024-11-05 23:10:56]
  • 评测
  • 测评结果:WA
  • 用时:144ms
  • 内存:37628kb
  • [2024-11-05 23:10:54]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

struct Node : public std::array<int, 26> {
    using std::array<int, 26>::array;

    Node operator+(const Node &y) const {
        Node ans;
        for(int i = 0; i < 26; i++) {
            ans[i] = (*this)[i] + y[i];
        }
        return ans;
    }

    Node operator-(const Node &y) const {
        Node ans;
        for(int i = 0; i < 26; i++) {
            ans[i] = (*this)[i] - y[i];
        }
        return ans;
    }

    Node operator*(const int x) const {
        Node ans = *this;
        for(int i = 0; i < 26; i++) {
            ans[i] *= x;
        }
        return ans;
    }

    bool empty() const {
        for(auto x : (*this)) {
            if(x != 0) {
                return false;
            }
        }
        return true;
    }

    bool operator!=(const Node &y) const {
        if(this->empty() || y.empty()) {
            return false;
        } else {
            return !((*this) == y);
        }
    }

    bool operator>(const Node &y) {
        for(int i = 0; i < 26; i++) {
            if((*this)[i] < y[i]) {
                return false;
            }
        }
        return true;
    }
};

void assign_string(string &s, int l, int r, Node node) {
    int p = 0;
    for(int i = l; i <= r; i++) {
        while(node[p] == 0) {
            p++;
        }
        s[i] = (char)('a' + p);
        node[p]--;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        vector<string> s(n);
        vector<int> sz(n);
        vector<Node> cnt(n);
        vector<vector<Node>> cst(n);
        for(int i = 0; i < n; i++) {
            cin >> s[i];
            for(auto ch : s[i]) {
                cnt[i][ch - 'a']++;
            }
            sz[i] = s[i].size();
            cst[i].resize(s[i].size());
        }
        cst[0].back() = cnt[0];
        bool fl = true;
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < s[i].size(); j++) {
                if(j < sz[i - 1]) {
                    cst[i][j] = cst[i - 1][j];
                } else if(!cst[i][j - sz[i - 1]].empty()) {
                    cst[i][j] = cst[i][j - sz[i - 1]] + cnt[i - 1];
                }
            }
            if(cst[i].back() != cnt[i]) {
                fl = false;
                break;
            }
            cst[i].back() = cnt[i];
            if(sz[i] % sz[i - 1] != 0 && sz[i] > sz[i - 1]) {
                auto t = cnt[i] - cnt[i - 1] * (sz[i] / sz[i - 1]);
                if(t != cst[i][(sz[i] - 1) % sz[i - 1]]) {
                    fl = false;
                    break;
                } else {
                    cst[i][(sz[i] - 1) % sz[i - 1]] = t;
                }
            }
        }

        for(int i = n - 2; i >= 0 && fl; i--) {
            for(int j = 0; j < std::min(s[i].size(), s[i + 1].size()); j++) {
                if(cst[i][j] != cst[i + 1][j]) {
                    fl = false;
                    break;
                } else if(!cst[i + 1][j].empty()) {
                    cst[i][j] = cst[i + 1][j];
                }
            }
        }

        for(int i = 1; i < n && fl; i++) {
            for(int j = 0; j < s[i].size(); j++) {
                if(j < sz[i - 1]) {
                    if(cst[i - 1][j] != cst[i][j]) {
                        fl = false;
                        break;
                    } else if(!cst[i - 1][j].empty()) {
                        cst[i][j] = cst[i - 1][j];
                    }
                } else if(!cst[i][j - sz[i - 1]].empty()) {
                    auto t = cst[i][j - sz[i - 1]] + cnt[i - 1];
                    if(t != cst[i][j]) {
                        fl = false;
                        break;
                    } else if(!t.empty()) {
                        cst[i][j] = t;
                    }
                }
            }
        }

        vector<string> ans = s;
        {
            int last = s[0].size() - 1;
            for(int j = s[0].size() - 2; j >= 0; j--) {
                if(!cst[0][j].empty()) {
                    if(cst[0][last] > cst[0][j]) {
                        assign_string(ans[0], j + 1, last, cst[0][last] - cst[0][j]);
                        last = j;
                    } else {
                        fl = false;
                        break;
                    }
                }
            }
            assign_string(ans[0], 0, last, cst[0][last]);
        }
        for(int i = 1; i < n && fl; i++) {
            for(int j = 0; j  < sz[i]; j++) {
                ans[i][j] = ans[i - 1][j % sz[i - 1]];
            }
        }

        if(fl) {
            cout << "YES" << endl;
            for(auto & str : ans) {
                cout << str << endl;
            }
        } else {
            cout << "NO" << endl;
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0ms
memory: 3620kb

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: 144ms
memory: 37628kb

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:

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