QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#714497#8234. Period of a StringRhineRE 1ms3568kbC++205.1kb2024-11-05 23:38:312024-11-05 23:38:31

Judging History

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

  • [2024-11-05 23:38:31]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3568kb
  • [2024-11-05 23:38:31]
  • 提交

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;
    }

    bool operator<<(const Node &y) {
        if((*this) != y) {
            return false;
        }
        if(!y.empty()) {
            (*this) = y;
        }
        return true;
    }
};

void assign_string(string &s, int l, int r, Node node) {
    int p = 0;
    for(int i = l; i <= r; i++) {
        while(p < 26 && 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 - 1; i > 0 && fl; i--) {
            for(int j = 0; j < sz[i] && fl; j++) {
                if(!cst[i][j].empty()) {
                    fl = (fl && (cst[i - 1][j % sz[i - 1]] << (cst[i][j] - cnt[i - 1] * (j / sz[i - 1]))));
                }
            }
        }

        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;
        for(int i = 0; i < n; i++){
            int last = s[i].size() - 1;
            for(int j = s[i].size() - 2; j >= 0; j--) {
                if(!cst[i][j].empty()) {
                    if(cst[i][last] > cst[i][j]) {
                        assign_string(ans[i], j + 1, last, cst[i][last] - cst[i][j]);
                        last = j;
                    } else {
                        fl = false;
                        break;
                    }
                }
            }
            assign_string(ans[i], 0, last, cst[i][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: 1ms
memory: 3568kb

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
Runtime Error

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: