QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#218110#2428. Comma SprinklerKronos#AC ✓339ms48264kbC++175.3kb2023-10-17 18:36:272023-10-17 18:36:27

Judging History

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

  • [2023-10-17 18:36:27]
  • 评测
  • 测评结果:AC
  • 用时:339ms
  • 内存:48264kb
  • [2023-10-17 18:36:27]
  • 提交

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("");
}

詳細信息

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