QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#356980#2428. Comma SprinklerSorting#WA 0ms3504kbC++203.0kb2024-03-18 16:55:102024-03-18 16:55:10

Judging History

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

  • [2024-03-18 16:55:10]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3504kb
  • [2024-03-18 16:55:10]
  • 提交

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 = 10000000000000061;
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";
}

Details

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3504kb