QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#505804#2428. Comma SprinklerRico64AC ✓207ms70292kbC++232.6kb2024-08-05 11:40:092024-08-05 11:40:10

Judging History

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

  • [2024-08-05 11:40:10]
  • 评测
  • 测评结果:AC
  • 用时:207ms
  • 内存:70292kb
  • [2024-08-05 11:40:09]
  • 提交

answer

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

int main() {
    string input;
    getline(cin, input);

    unordered_map<string, int> sti;
    vector<pair<int, pair<int, int>>> blocks;
    for (int i = 0, l = -1; i < input.size(); ++i) {
        char c = input[i];
        if (c >= 'a' && c <= 'z') {
            if (l == -1) l = i;
        } else {
            if (l >= 0) {
                string ss = input.substr(l, i - l);
                int id;
                if (sti.count(ss)) {
                    id = sti[ss];
                } else {
                    id = sti.size();
                }
                sti[ss] = id;
                blocks.push_back({id, {l, i}});
                l = -1;
            }
        }
    }

//    for (const auto& p : sti) cout << p.first << " : " << p.second << endl;

    int n = sti.size();
    unordered_set<int> graph[n * 2];
    bool colored[n * 2];
    fill(colored, colored + n * 2, false);
    for (int i = 1; i < blocks.size(); ++i) {
        if (blocks[i].second.first - blocks[i-1].second.second == 1) {
            graph[blocks[i-1].first * 2 + 1].insert(blocks[i].first * 2);
            graph[blocks[i].first * 2].insert(blocks[i-1].first * 2 + 1);
        } else if (input[blocks[i-1].second.second] == ',') {
            colored[blocks[i-1].first * 2 + 1] = true;
            colored[blocks[i].first * 2] = true;
        }
    }

//    for (int x = 0; x < n * 2; ++x) {
//        cout << x << " : ";
//        for (const int& y : graph[x]) {
//            cout << y << ",";
//        }
//        cout << endl;
//    }

    queue<int> q;
    for (int i = 0; i < n * 2; ++i) {
        if (colored[i]) {
            q.push(i);
        }
    }
    fill(colored, colored + n * 2, false);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        if (colored[v]) continue;
        colored[v] = true;
        for (const int& ne : graph[v]) {
            if (colored[ne]) continue;
            q.push(ne);
        }
    }

    for (int i = 0; i < blocks.size(); ++i) {
        cout << input.substr(blocks[i].second.first, blocks[i].second.second - blocks[i].second.first);
        if (i == blocks.size() - 1) {
            cout << input.substr(blocks[i].second.second);
        } else if (blocks[i + 1].second.first - blocks[i].second.second > 1 || !colored[blocks[i].first * 2 + 1]) {
            cout << input.substr(blocks[i].second.second, blocks[i + 1].second.first - blocks[i].second.second);
        } else {
            cout << ", ";
        }
    }
    cout << endl;

    return 0;
}

詳細信息

Test #1:

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

Test #2:

score: 0
Accepted
time: 0ms
memory: 3572kb

Test #3:

score: 0
Accepted
time: 0ms
memory: 3816kb

Test #4:

score: 0
Accepted
time: 0ms
memory: 3596kb

Test #5:

score: 0
Accepted
time: 0ms
memory: 3568kb

Test #6:

score: 0
Accepted
time: 38ms
memory: 12912kb

Test #7:

score: 0
Accepted
time: 81ms
memory: 56528kb

Test #8:

score: 0
Accepted
time: 79ms
memory: 56544kb

Test #9:

score: 0
Accepted
time: 0ms
memory: 3744kb

Test #10:

score: 0
Accepted
time: 0ms
memory: 3828kb

Test #11:

score: 0
Accepted
time: 0ms
memory: 3652kb

Test #12:

score: 0
Accepted
time: 0ms
memory: 3604kb

Test #13:

score: 0
Accepted
time: 1ms
memory: 3928kb

Test #14:

score: 0
Accepted
time: 0ms
memory: 3680kb

Test #15:

score: 0
Accepted
time: 0ms
memory: 3816kb

Test #16:

score: 0
Accepted
time: 110ms
memory: 21172kb

Test #17:

score: 0
Accepted
time: 207ms
memory: 35680kb

Test #18:

score: 0
Accepted
time: 190ms
memory: 61488kb

Test #19:

score: 0
Accepted
time: 0ms
memory: 3592kb

Test #20:

score: 0
Accepted
time: 162ms
memory: 70292kb

Test #21:

score: 0
Accepted
time: 95ms
memory: 70020kb

Test #22:

score: 0
Accepted
time: 72ms
memory: 64716kb

Test #23:

score: 0
Accepted
time: 17ms
memory: 14532kb

Test #24:

score: 0
Accepted
time: 106ms
memory: 44772kb

Test #25:

score: 0
Accepted
time: 49ms
memory: 25164kb

Test #26:

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

Test #27:

score: 0
Accepted
time: 49ms
memory: 24284kb

Test #28:

score: 0
Accepted
time: 78ms
memory: 35660kb

Test #29:

score: 0
Accepted
time: 4ms
memory: 5256kb

Test #30:

score: 0
Accepted
time: 0ms
memory: 3608kb

Test #31:

score: 0
Accepted
time: 6ms
memory: 5476kb

Test #32:

score: 0
Accepted
time: 14ms
memory: 5344kb

Test #33:

score: 0
Accepted
time: 0ms
memory: 3516kb

Test #34:

score: 0
Accepted
time: 0ms
memory: 3632kb

Test #35:

score: 0
Accepted
time: 0ms
memory: 3480kb

Test #36:

score: 0
Accepted
time: 0ms
memory: 3808kb

Test #37:

score: 0
Accepted
time: 0ms
memory: 3744kb

Test #38:

score: 0
Accepted
time: 0ms
memory: 3820kb

Test #39:

score: 0
Accepted
time: 0ms
memory: 3472kb

Test #40:

score: 0
Accepted
time: 0ms
memory: 3772kb

Test #41:

score: 0
Accepted
time: 9ms
memory: 8008kb

Test #42:

score: 0
Accepted
time: 9ms
memory: 8060kb

Test #43:

score: 0
Accepted
time: 3ms
memory: 8104kb

Test #44:

score: 0
Accepted
time: 6ms
memory: 8392kb

Test #45:

score: 0
Accepted
time: 4ms
memory: 8372kb

Test #46:

score: 0
Accepted
time: 4ms
memory: 8384kb

Test #47:

score: 0
Accepted
time: 55ms
memory: 20436kb

Test #48:

score: 0
Accepted
time: 58ms
memory: 20416kb

Test #49:

score: 0
Accepted
time: 55ms
memory: 20476kb

Test #50:

score: 0
Accepted
time: 28ms
memory: 14796kb

Test #51:

score: 0
Accepted
time: 33ms
memory: 14772kb

Test #52:

score: 0
Accepted
time: 29ms
memory: 14940kb

Test #53:

score: 0
Accepted
time: 157ms
memory: 30972kb

Test #54:

score: 0
Accepted
time: 155ms
memory: 31140kb

Test #55:

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

Test #56:

score: 0
Accepted
time: 121ms
memory: 26380kb

Test #57:

score: 0
Accepted
time: 121ms
memory: 26192kb

Test #58:

score: 0
Accepted
time: 120ms
memory: 26496kb

Test #59:

score: 0
Accepted
time: 0ms
memory: 3772kb

Test #60:

score: 0
Accepted
time: 14ms
memory: 6112kb

Test #61:

score: 0
Accepted
time: 9ms
memory: 5180kb

Test #62:

score: 0
Accepted
time: 0ms
memory: 3608kb