QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#356975#2428. Comma SprinklerSorting#WA 370ms52948kbC++203.0kb2024-03-18 16:52:492024-03-18 16:52:49

Judging History

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

  • [2024-03-18 16:52:49]
  • 评测
  • 测评结果:WA
  • 用时:370ms
  • 内存:52948kb
  • [2024-03-18 16:52:49]
  • 提交

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 = 1e9 + 7;
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(int)> 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";
}

详细

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

score: 0
Accepted
time: 44ms
memory: 49292kb

Test #7:

score: 0
Accepted
time: 150ms
memory: 52856kb

Test #8:

score: 0
Accepted
time: 159ms
memory: 52948kb

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

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

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

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

Test #17:

score: 0
Accepted
time: 244ms
memory: 29056kb

Test #18:

score: 0
Accepted
time: 347ms
memory: 42644kb

Test #19:

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

Test #20:

score: 0
Accepted
time: 370ms
memory: 46748kb

Test #21:

score: -100
Wrong Answer
time: 249ms
memory: 42860kb