QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372786 | #2428. Comma Sprinkler | TWTP_TCTF# | AC ✓ | 180ms | 125724kb | C++14 | 2.4kb | 2024-03-31 19:10:55 | 2024-03-31 19:10:56 |
Judging History
answer
#include<iostream>
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 2e6 + 2, MOD = 998244353;
map<string, int> id;
int getID(string s) {
if (s.back() == '.')s.pop_back();
if (s.back() == ',')s.pop_back();
if (id.find(s) == id.end())id[s] = id.size();
return id[s];
}
vector<pair<string, int>> getWords(string &s) {
vector<pair<string, int>> v;
string temp = "";
s += " ";
for (auto i: s) {
if (i == ' ') {
v.push_back({temp, getID(temp)});
temp = "";
} else {
temp += i;
}
}
return v;
}
vector<int> adj_before[N], adj_after[N];
void doWork() {
string s;
getline(cin, s);
vector<pair<string, int>> v = getWords(s);
queue<int> q_after, q_before;
for (int i = 0; i < v.size(); i++) {
adj_before[v[i].second].push_back(i);
adj_after[v[i].second].push_back(i);
if (v[i].first.back() == ',') {
q_after.push(i);
}
if (i && v[i - 1].first.back() == ',') {
q_before.push(i);
}
}
while (!q_after.empty() || !q_before.empty()) {
if (!q_after.empty()) {
int node = q_after.front();
q_after.pop();
int g = v[node].second;
for (auto i: adj_after[g]) {
if (v[i].first.back() == '.' || v[i].first.back() == ',')continue;
v[i].first += ',';
if (i + 1 < v.size()) {
q_before.push(i + 1);
}
}
adj_after[g].clear();
} else {
int node = q_before.front();
q_before.pop();
int g = v[node].second;
for (auto i: adj_before[g]) {
if (i == 0 || v[i - 1].first.back() == '.' || v[i - 1].first.back() == ',')continue;
v[i - 1].first += ',';
q_after.push(i - 1);
}
adj_before[g].clear();
}
}
for (auto i: v) {
cout << i.first << " ";
}
}
int main() {
IO
int t = 1;
// cin >> t;
for (int i = 1; i <= t; i++) {
// cout << "Case #" << i << ": ";
doWork();
}
}
Details
Test #1:
score: 100
Accepted
time: 3ms
memory: 97544kb
Test #2:
score: 0
Accepted
time: 7ms
memory: 97352kb
Test #3:
score: 0
Accepted
time: 12ms
memory: 97328kb
Test #4:
score: 0
Accepted
time: 7ms
memory: 97528kb
Test #5:
score: 0
Accepted
time: 7ms
memory: 97288kb
Test #6:
score: 0
Accepted
time: 51ms
memory: 123972kb
Test #7:
score: 0
Accepted
time: 107ms
memory: 120444kb
Test #8:
score: 0
Accepted
time: 95ms
memory: 120072kb
Test #9:
score: 0
Accepted
time: 3ms
memory: 97528kb
Test #10:
score: 0
Accepted
time: 4ms
memory: 97400kb
Test #11:
score: 0
Accepted
time: 13ms
memory: 97332kb
Test #12:
score: 0
Accepted
time: 11ms
memory: 97376kb
Test #13:
score: 0
Accepted
time: 11ms
memory: 97308kb
Test #14:
score: 0
Accepted
time: 7ms
memory: 97632kb
Test #15:
score: 0
Accepted
time: 3ms
memory: 97320kb
Test #16:
score: 0
Accepted
time: 101ms
memory: 121276kb
Test #17:
score: 0
Accepted
time: 146ms
memory: 120692kb
Test #18:
score: 0
Accepted
time: 176ms
memory: 125724kb
Test #19:
score: 0
Accepted
time: 11ms
memory: 97376kb
Test #20:
score: 0
Accepted
time: 180ms
memory: 125264kb
Test #21:
score: 0
Accepted
time: 166ms
memory: 125364kb
Test #22:
score: 0
Accepted
time: 155ms
memory: 121992kb
Test #23:
score: 0
Accepted
time: 35ms
memory: 103776kb
Test #24:
score: 0
Accepted
time: 171ms
memory: 123300kb
Test #25:
score: 0
Accepted
time: 161ms
memory: 122744kb
Test #26:
score: 0
Accepted
time: 171ms
memory: 122468kb
Test #27:
score: 0
Accepted
time: 142ms
memory: 120116kb
Test #28:
score: 0
Accepted
time: 155ms
memory: 123768kb
Test #29:
score: 0
Accepted
time: 20ms
memory: 99756kb
Test #30:
score: 0
Accepted
time: 8ms
memory: 97292kb
Test #31:
score: 0
Accepted
time: 11ms
memory: 100604kb
Test #32:
score: 0
Accepted
time: 11ms
memory: 99720kb
Test #33:
score: 0
Accepted
time: 12ms
memory: 97344kb
Test #34:
score: 0
Accepted
time: 9ms
memory: 97372kb
Test #35:
score: 0
Accepted
time: 7ms
memory: 97380kb
Test #36:
score: 0
Accepted
time: 11ms
memory: 97312kb
Test #37:
score: 0
Accepted
time: 4ms
memory: 97356kb
Test #38:
score: 0
Accepted
time: 8ms
memory: 97252kb
Test #39:
score: 0
Accepted
time: 7ms
memory: 97352kb
Test #40:
score: 0
Accepted
time: 8ms
memory: 97344kb
Test #41:
score: 0
Accepted
time: 24ms
memory: 99216kb
Test #42:
score: 0
Accepted
time: 16ms
memory: 99028kb
Test #43:
score: 0
Accepted
time: 24ms
memory: 99068kb
Test #44:
score: 0
Accepted
time: 20ms
memory: 99064kb
Test #45:
score: 0
Accepted
time: 16ms
memory: 98996kb
Test #46:
score: 0
Accepted
time: 20ms
memory: 99064kb
Test #47:
score: 0
Accepted
time: 60ms
memory: 105648kb
Test #48:
score: 0
Accepted
time: 51ms
memory: 105592kb
Test #49:
score: 0
Accepted
time: 63ms
memory: 105644kb
Test #50:
score: 0
Accepted
time: 47ms
memory: 105128kb
Test #51:
score: 0
Accepted
time: 49ms
memory: 104764kb
Test #52:
score: 0
Accepted
time: 42ms
memory: 104664kb
Test #53:
score: 0
Accepted
time: 106ms
memory: 112792kb
Test #54:
score: 0
Accepted
time: 100ms
memory: 112864kb
Test #55:
score: 0
Accepted
time: 91ms
memory: 112884kb
Test #56:
score: 0
Accepted
time: 96ms
memory: 112508kb
Test #57:
score: 0
Accepted
time: 94ms
memory: 111384kb
Test #58:
score: 0
Accepted
time: 78ms
memory: 112032kb
Test #59:
score: 0
Accepted
time: 10ms
memory: 97312kb
Test #60:
score: 0
Accepted
time: 11ms
memory: 101920kb
Test #61:
score: 0
Accepted
time: 17ms
memory: 98956kb
Test #62:
score: 0
Accepted
time: 7ms
memory: 97304kb