QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#356975 | #2428. Comma Sprinkler | Sorting# | WA | 370ms | 52948kb | C++20 | 3.0kb | 2024-03-18 16:52:49 | 2024-03-18 16:52:49 |
Judging History
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