QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#356995#2428. Comma SprinklerSorting#AC ✓543ms70752kbC++203.0kb2024-03-18 17:05:442024-03-18 17:05:45

Judging History

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

  • [2024-03-18 17:05:45]
  • 评测
  • 测评结果:AC
  • 用时:543ms
  • 内存:70752kb
  • [2024-03-18 17:05:44]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <set>
#include <map>
#include <array>
#include <functional>

using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()

const ll MOD = 10000000000000061ll;
const ll BASE = 37;

string s;

ll get_hash(const string &word){
    ll hsh = 0;
    for(char c: word){
        hsh *= BASE;
        hsh += c - 'a' + 1;
        hsh %= MOD;
    }
    return hsh;
}

ll get_r_hash(const string &word){
    ll h = get_hash(word);
    return MOD + h;
}

map<ll, vector<ll>> adj;
set<ll> active;
set<ll> vis;

void process_sentence(const vector<string> &sentence){
    for(int i = 0; i < sentence.size(); ++i){
        if(sentence[i] == ","){
            active.insert(get_hash(sentence[i - 1]));
            active.insert(get_r_hash(sentence[i + 1]));
            continue;
        }
        if(i != 0){
            ll h1, h2;
            if(sentence[i - 1] != ","){
                h1 = get_r_hash(sentence[i]);
                h2 = get_hash(sentence[i - 1]);
            }
            else{
                h1 = get_r_hash(sentence[i]);
                h2 = get_hash(sentence[i - 2]);
            }

            adj[h1].push_back(h2);
            adj[h2].push_back(h1);
        }
    }
}

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

    getline(cin, s);

    string word = "";
    vector<string> sentence;
    vector<vector<string>> all_s;
    for(int i = 0; i < s.size(); ++i){
        // cout << i << " i" << endl; 
        if(s[i] == ' '){
            sentence.push_back(word);
            word = "";
            continue;
        }
        if(s[i] == ','){
            sentence.push_back(word);
            sentence.push_back(",");
            ++i;
            word = "";
            continue;
        }
        if(s[i] == '.'){
            sentence.push_back(word);
            process_sentence(sentence);
            word = "";
            all_s.push_back(sentence);
            sentence.clear();
            ++i;
            continue;
        }
        word += s[i];
    }

    function<void(ll)> dfs = [&](ll x){
        vis.insert(x);

        for(ll to: adj[x]){
            if(vis.count(to)) continue;
            dfs(to);
        }
    };

    for(ll x: active){
        if(vis.count(x)) continue;
        dfs(x);
    }

    for(int j = 0; j < all_s.size(); ++j){
        auto &sentence = all_s[j];

        for(int i = 0; i < sentence.size(); ++i){
            auto &word = sentence[i];
            if(word == ",") continue;
            cout << word;
            if(i == (int)sentence.size() - 1){
                cout << ".";
                if(j != (int)all_s.size() - 1){
                    cout << " ";
                }
                continue;
            }
            if(vis.count(get_hash(word))){
                cout << ",";
            }
            cout << " ";
        }
    }
    cout << "\n";
}

Details

Test #1:

score: 100
Accepted
time: 1ms
memory: 3596kb

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

score: 0
Accepted
time: 153ms
memory: 50780kb

Test #8:

score: 0
Accepted
time: 158ms
memory: 51572kb

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

score: 0
Accepted
time: 131ms
memory: 26928kb

Test #17:

score: 0
Accepted
time: 235ms
memory: 29104kb

Test #18:

score: 0
Accepted
time: 373ms
memory: 42424kb

Test #19:

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

Test #20:

score: 0
Accepted
time: 410ms
memory: 46668kb

Test #21:

score: 0
Accepted
time: 299ms
memory: 42692kb

Test #22:

score: 0
Accepted
time: 219ms
memory: 38488kb

Test #23:

score: 0
Accepted
time: 22ms
memory: 10244kb

Test #24:

score: 0
Accepted
time: 476ms
memory: 51644kb

Test #25:

score: 0
Accepted
time: 543ms
memory: 70752kb

Test #26:

score: 0
Accepted
time: 167ms
memory: 31836kb

Test #27:

score: 0
Accepted
time: 22ms
memory: 19012kb

Test #28:

score: 0
Accepted
time: 378ms
memory: 45976kb

Test #29:

score: 0
Accepted
time: 13ms
memory: 5228kb

Test #30:

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

Test #31:

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

Test #32:

score: 0
Accepted
time: 20ms
memory: 6332kb

Test #33:

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

Test #34:

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

Test #35:

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

Test #36:

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

Test #37:

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

Test #38:

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

Test #39:

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

Test #40:

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

Test #41:

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

Test #42:

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

Test #43:

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

Test #44:

score: 0
Accepted
time: 10ms
memory: 6404kb

Test #45:

score: 0
Accepted
time: 10ms
memory: 6308kb

Test #46:

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

Test #47:

score: 0
Accepted
time: 84ms
memory: 16700kb

Test #48:

score: 0
Accepted
time: 80ms
memory: 16528kb

Test #49:

score: 0
Accepted
time: 82ms
memory: 16608kb

Test #50:

score: 0
Accepted
time: 40ms
memory: 12960kb

Test #51:

score: 0
Accepted
time: 50ms
memory: 12908kb

Test #52:

score: 0
Accepted
time: 46ms
memory: 12924kb

Test #53:

score: 0
Accepted
time: 167ms
memory: 24504kb

Test #54:

score: 0
Accepted
time: 160ms
memory: 24472kb

Test #55:

score: 0
Accepted
time: 172ms
memory: 24468kb

Test #56:

score: 0
Accepted
time: 137ms
memory: 23128kb

Test #57:

score: 0
Accepted
time: 146ms
memory: 23292kb

Test #58:

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

Test #59:

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

Test #60:

score: 0
Accepted
time: 2ms
memory: 7300kb

Test #61:

score: 0
Accepted
time: 10ms
memory: 6404kb

Test #62:

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