QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#356995 | #2428. Comma Sprinkler | Sorting# | AC ✓ | 543ms | 70752kb | C++20 | 3.0kb | 2024-03-18 17:05:44 | 2024-03-18 17:05:45 |
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 = 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