QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#218110 | #2428. Comma Sprinkler | Kronos# | AC ✓ | 339ms | 48264kb | C++17 | 5.3kb | 2023-10-17 18:36:27 | 2023-10-17 18:36:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
struct debug {
#define contPrint { *this << "["; \
int f = 0; for(auto it : x) { *this << (f?", ":""); *this << it; f = 1;} \
*this << "]"; return *this;}
~debug(){cerr << endl;}
template<class c> debug& operator<<(c x) {cerr << x; return *this;}
template<class c, class d>
debug& operator<<(pair<c, d> x) {*this << "(" << x.first << ", " << x.second << ")";
return *this;}
template<class c> debug& operator<<(vector<c> x) contPrint;
template<class c> debug& operator<<(deque<c> x) contPrint;
template<class c> debug& operator<<(set<c> x) contPrint;
template<class c> debug& operator<<(multiset<c> x) contPrint;
template<class c, class d> debug& operator<<(map<c, d> x) contPrint;
template<class c, class d> debug& operator<<(unordered_map<c, d> x) contPrint;
#undef contPrint
};
#define dbg(x) "[" << #x << ": " << x << "] "
#define Wa() cerr << "[LINE: " << __LINE__ << "] -> "; debug() <<
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
const int N = 1e6 + 6;
char ch[N];
vector<int> pos[N];
int main()
{
vector<string> v;
while(scanf("%s", ch) != EOF) {
string s = ch;
if(s.back() == '.' || s.back() == ',') s.pop_back();
v.push_back(string(ch));
}
int sz = (int)v.size();
vector<int> str_ids(sz);
{
map<string, int> id;
int cur = 1;
for(int i = 0; i < sz; i++) {
auto it = v[i];
if(it.back() == ',' || it.back() == '.') it.pop_back();
if(id[it] == 0) {
id[it] = cur++;
}
str_ids[i] = id[it];
}
}
// map<int, vector<int>> pos;
for(int i = 0; i < sz; i++) {
pos[str_ids[i]].push_back(i);
}
queue<pair<int, int>> q;
set<int> bef, aft;
for(int i = 0; i < sz; i++) {
if(i) {
if(v[i-1].back() == ',') {
if(v[i].back() == '.') {
// v[i].pop_back();
if(bef.find(str_ids[i]) == bef.end()) {
bef.insert(str_ids[i]);
q.push({str_ids[i], 0});
}
// v[i].push_back('.');
} else if (v[i].back() == ','){
// v[i].pop_back();
if(bef.find(str_ids[i]) == bef.end()) {
bef.insert(str_ids[i]);
q.push({str_ids[i], 0});
}
// v[i].push_back(',');
} else {
if(bef.find(str_ids[i]) == bef.end()) {
bef.insert(str_ids[i]);
q.push({str_ids[i], 0});
}
}
}
}
if(v[i].back() == ',') {
v[i].pop_back();
if(aft.find(str_ids[i]) == aft.end()) {
aft.insert(str_ids[i]);
q.push({str_ids[i], 1});
}
v[i].push_back(',');
}
}
while(!q.empty()) {
auto [cur, t] = q.front(); q.pop();
// Wa() dbg(cur) dbg(t) dbg(pos[cur]);
if(t == 0) {
for(int p : pos[cur]) {
if(p) {
char c = '#';
if(v[p-1].back() == '.' || v[p-1].back() ==',') {
c = v[p-1].back();
v[p-1].pop_back();
}
if(c == '#' && aft.find(str_ids[p-1]) == aft.end()) {
q.push({str_ids[p-1], 1});
aft.insert(str_ids[p-1]);
}
if(c != '#') {
v[p-1].push_back(c);
}
}
}
}
if(t == 1) {
for(int p : pos[cur]) {
if(p < sz-1) {
if(v[p].back() == '.') continue;
char c = '#';
if(v[p+1].back() == '.' || v[p+1].back() == ',') {
c = v[p+1].back();
v[p+1].pop_back();
}
if(bef.find(str_ids[p+1]) == bef.end()) {
q.push({str_ids[p+1], 0});
bef.insert(str_ids[p+1]);
}
if(c != '#') {
v[p+1].push_back(c);
}
}
}
}
}
// Wa() dbg(bef) dbg(aft);
for(int i = 0; i < sz; i++) {
auto s = v[i];
if(s.back() == ',' || s.back() == '.') s.pop_back();
if(aft.find(str_ids[i]) != aft.end()) {
if(v[i].back() != '.' and v[i].back() != ',') {
v[i] += ',';
}
}
if(i) {
if(bef.find(str_ids[i]) != bef.end()) {
if(v[i-1].back() != '.' && v[i-1].back() != ',') {
v[i-1] += ',';
}
}
}
}
// Wa() dbg(aft) dbg(bef);
for(int i = 0; i < sz; i++) {
if(i) printf(" ");
printf("%s", v[i].c_str());
}
puts("");
}
Details
Test #1:
score: 100
Accepted
time: 0ms
memory: 27064kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 27136kb
Test #3:
score: 0
Accepted
time: 3ms
memory: 27100kb
Test #4:
score: 0
Accepted
time: 7ms
memory: 27044kb
Test #5:
score: 0
Accepted
time: 3ms
memory: 27100kb
Test #6:
score: 0
Accepted
time: 76ms
memory: 48264kb
Test #7:
score: 0
Accepted
time: 154ms
memory: 41528kb
Test #8:
score: 0
Accepted
time: 151ms
memory: 41488kb
Test #9:
score: 0
Accepted
time: 0ms
memory: 27104kb
Test #10:
score: 0
Accepted
time: 0ms
memory: 27068kb
Test #11:
score: 0
Accepted
time: 0ms
memory: 27200kb
Test #12:
score: 0
Accepted
time: 7ms
memory: 27112kb
Test #13:
score: 0
Accepted
time: 7ms
memory: 27156kb
Test #14:
score: 0
Accepted
time: 3ms
memory: 27084kb
Test #15:
score: 0
Accepted
time: 11ms
memory: 27052kb
Test #16:
score: 0
Accepted
time: 170ms
memory: 43196kb
Test #17:
score: 0
Accepted
time: 279ms
memory: 43048kb
Test #18:
score: 0
Accepted
time: 339ms
memory: 46752kb
Test #19:
score: 0
Accepted
time: 0ms
memory: 27104kb
Test #20:
score: 0
Accepted
time: 323ms
memory: 46220kb
Test #21:
score: 0
Accepted
time: 220ms
memory: 42808kb
Test #22:
score: 0
Accepted
time: 183ms
memory: 41336kb
Test #23:
score: 0
Accepted
time: 28ms
memory: 31220kb
Test #24:
score: 0
Accepted
time: 294ms
memory: 46288kb
Test #25:
score: 0
Accepted
time: 271ms
memory: 47584kb
Test #26:
score: 0
Accepted
time: 237ms
memory: 42560kb
Test #27:
score: 0
Accepted
time: 146ms
memory: 41352kb
Test #28:
score: 0
Accepted
time: 271ms
memory: 44784kb
Test #29:
score: 0
Accepted
time: 8ms
memory: 29136kb
Test #30:
score: 0
Accepted
time: 3ms
memory: 27108kb
Test #31:
score: 0
Accepted
time: 3ms
memory: 29392kb
Test #32:
score: 0
Accepted
time: 5ms
memory: 28904kb
Test #33:
score: 0
Accepted
time: 0ms
memory: 27036kb
Test #34:
score: 0
Accepted
time: 0ms
memory: 27132kb
Test #35:
score: 0
Accepted
time: 3ms
memory: 27104kb
Test #36:
score: 0
Accepted
time: 7ms
memory: 27104kb
Test #37:
score: 0
Accepted
time: 3ms
memory: 27128kb
Test #38:
score: 0
Accepted
time: 4ms
memory: 27096kb
Test #39:
score: 0
Accepted
time: 4ms
memory: 27052kb
Test #40:
score: 0
Accepted
time: 0ms
memory: 27096kb
Test #41:
score: 0
Accepted
time: 13ms
memory: 28264kb
Test #42:
score: 0
Accepted
time: 11ms
memory: 28132kb
Test #43:
score: 0
Accepted
time: 20ms
memory: 28264kb
Test #44:
score: 0
Accepted
time: 13ms
memory: 28228kb
Test #45:
score: 0
Accepted
time: 15ms
memory: 28132kb
Test #46:
score: 0
Accepted
time: 7ms
memory: 28112kb
Test #47:
score: 0
Accepted
time: 89ms
memory: 33328kb
Test #48:
score: 0
Accepted
time: 88ms
memory: 33488kb
Test #49:
score: 0
Accepted
time: 90ms
memory: 33368kb
Test #50:
score: 0
Accepted
time: 61ms
memory: 31468kb
Test #51:
score: 0
Accepted
time: 70ms
memory: 31512kb
Test #52:
score: 0
Accepted
time: 69ms
memory: 31648kb
Test #53:
score: 0
Accepted
time: 172ms
memory: 38716kb
Test #54:
score: 0
Accepted
time: 177ms
memory: 38680kb
Test #55:
score: 0
Accepted
time: 187ms
memory: 38712kb
Test #56:
score: 0
Accepted
time: 159ms
memory: 37404kb
Test #57:
score: 0
Accepted
time: 156ms
memory: 37392kb
Test #58:
score: 0
Accepted
time: 166ms
memory: 37212kb
Test #59:
score: 0
Accepted
time: 3ms
memory: 27044kb
Test #60:
score: 0
Accepted
time: 9ms
memory: 30696kb
Test #61:
score: 0
Accepted
time: 0ms
memory: 28088kb
Test #62:
score: 0
Accepted
time: 7ms
memory: 27132kb