QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#218070#2428. Comma SprinklerKronos#TL 3662ms38684kbC++174.5kb2023-10-17 18:01:542023-10-17 18:01:54

Judging History

你现在查看的是最新测评结果

  • [2023-10-17 18:01:54]
  • 评测
  • 测评结果:TL
  • 用时:3662ms
  • 内存:38684kb
  • [2023-10-17 18:01:54]
  • 提交

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];

int main()
{
    map<string, vector<int>> pos;
    vector<string> v;
    while(scanf("%s", ch) != EOF) {
        string s = ch;
        if(s.back() == '.' || s.back() == ',') s.pop_back();
        pos[s].push_back(v.size());
        v.push_back(string(ch));
    }

    int sz = (int)v.size();

    queue<pair<string, int>> q;
    set<string> 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(v[i]);
                    q.push({v[i], 0});
                    v[i].push_back('.');

                } else if (v[i].back() == ','){
                    v[i].pop_back();
                    bef.insert(v[i]);
                    q.push({v[i], 0});
                    v[i].push_back(',');

                } else {
                    bef.insert(v[i]);
                    q.push({v[i], 0});
                }
            }
        }

        if(v[i].back() == ',') {
            v[i].pop_back();
            aft.insert(v[i]);
            q.push({v[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(v[p-1]) == aft.end()) {


                        q.push({v[p-1], 1});
                        aft.insert(v[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(v[p+1]) == bef.end()) {
                        q.push({v[p+1], 0});
                        bef.insert(v[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(s) != aft.end()) {
            if(v[i].back() != '.' and v[i].back() != ',') {
                v[i] += ',';
            }
        }

        if(i) {
            if(bef.find(s) != 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: 1ms
memory: 3732kb

Test #2:

score: 0
Accepted
time: 0ms
memory: 3696kb

Test #3:

score: 0
Accepted
time: 1ms
memory: 3692kb

Test #4:

score: 0
Accepted
time: 0ms
memory: 3692kb

Test #5:

score: 0
Accepted
time: 1ms
memory: 3692kb

Test #6:

score: 0
Accepted
time: 64ms
memory: 22740kb

Test #7:

score: 0
Accepted
time: 147ms
memory: 29940kb

Test #8:

score: 0
Accepted
time: 165ms
memory: 29940kb

Test #9:

score: 0
Accepted
time: 0ms
memory: 3600kb

Test #10:

score: 0
Accepted
time: 1ms
memory: 3704kb

Test #11:

score: 0
Accepted
time: 1ms
memory: 3736kb

Test #12:

score: 0
Accepted
time: 0ms
memory: 3616kb

Test #13:

score: 0
Accepted
time: 0ms
memory: 3668kb

Test #14:

score: 0
Accepted
time: 1ms
memory: 3664kb

Test #15:

score: 0
Accepted
time: 1ms
memory: 3676kb

Test #16:

score: 0
Accepted
time: 3662ms
memory: 21372kb

Test #17:

score: 0
Accepted
time: 2207ms
memory: 23292kb

Test #18:

score: 0
Accepted
time: 1713ms
memory: 36128kb

Test #19:

score: 0
Accepted
time: 1ms
memory: 3728kb

Test #20:

score: 0
Accepted
time: 1092ms
memory: 38684kb

Test #21:

score: 0
Accepted
time: 452ms
memory: 32364kb

Test #22:

score: 0
Accepted
time: 307ms
memory: 28124kb

Test #23:

score: 0
Accepted
time: 24ms
memory: 8676kb

Test #24:

score: -100
Time Limit Exceeded