QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#218103 | #2428. Comma Sprinkler | Kronos# | TL | 1831ms | 48172kb | C++17 | 5.0kb | 2023-10-17 18:32:39 | 2023-10-17 18:32:39 |
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();
bef.insert(str_ids[i]);
q.push({str_ids[i], 0});
// v[i].push_back('.');
} else if (v[i].back() == ','){
// v[i].pop_back();
bef.insert(str_ids[i]);
q.push({str_ids[i], 0});
// v[i].push_back(',');
} else {
bef.insert(str_ids[i]);
q.push({str_ids[i], 0});
}
}
}
if(v[i].back() == ',') {
v[i].pop_back();
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: 27160kb
Test #2:
score: 0
Accepted
time: 0ms
memory: 27156kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 27100kb
Test #4:
score: 0
Accepted
time: 3ms
memory: 27064kb
Test #5:
score: 0
Accepted
time: 0ms
memory: 27104kb
Test #6:
score: 0
Accepted
time: 65ms
memory: 48172kb
Test #7:
score: 0
Accepted
time: 156ms
memory: 41440kb
Test #8:
score: 0
Accepted
time: 147ms
memory: 41436kb
Test #9:
score: 0
Accepted
time: 5ms
memory: 27112kb
Test #10:
score: 0
Accepted
time: 3ms
memory: 27080kb
Test #11:
score: 0
Accepted
time: 3ms
memory: 27164kb
Test #12:
score: 0
Accepted
time: 7ms
memory: 27048kb
Test #13:
score: 0
Accepted
time: 3ms
memory: 27092kb
Test #14:
score: 0
Accepted
time: 3ms
memory: 27132kb
Test #15:
score: 0
Accepted
time: 0ms
memory: 27168kb
Test #16:
score: 0
Accepted
time: 1831ms
memory: 43188kb
Test #17:
score: 0
Accepted
time: 1263ms
memory: 43084kb
Test #18:
score: 0
Accepted
time: 841ms
memory: 46752kb
Test #19:
score: 0
Accepted
time: 7ms
memory: 27060kb
Test #20:
score: 0
Accepted
time: 544ms
memory: 46252kb
Test #21:
score: 0
Accepted
time: 261ms
memory: 42836kb
Test #22:
score: 0
Accepted
time: 182ms
memory: 41204kb
Test #23:
score: 0
Accepted
time: 17ms
memory: 31332kb
Test #24:
score: -100
Time Limit Exceeded