Submission #704890

#	Time	Username	Problem	Language	Result	Execution time	Memory
704890		Cyanmond	Crossing (JOI21_crossing)	C++17	26 / 100	7015 ms	7812 KiB

Main

#include <bits/stdc++.h>

std::string cross(const std::string &a, const std::string &b) {
    std::string c;
    c.reserve(a.size());
    for (int i = 0; i < (int)a.size(); ++i) {
        if (a[i] == b[i]) {
            c.push_back(a[i]);
        } else {
            char x = 'J' xor 'O' xor 'I';
            x ^= a[i];
            x ^= b[i];
            c.push_back(x);
        }
    }
    return c;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N;
    std::cin >> N;
    std::string S1, S2, S3;
    std::cin >> S1 >> S2 >> S3;
    int Q;
    std::cin >> Q;
    std::string T0;
    std::cin >> T0;
    std::vector<int> L(Q), R(Q);
    std::vector<char> C(Q);
    for (int i = 0; i < Q; ++i) {
        std::cin >> L[i] >> R[i] >> C[i];
        --L[i];
    }

    std::set<std::string> flowers;
    std::queue<std::string> ns;
    ns.push(S1);
    ns.push(S2);
    ns.push(S3);
    flowers.insert(S1);
    flowers.insert(S2);
    flowers.insert(S3);
    while (not ns.empty()) {
        const auto t = ns.front();
        ns.pop();
        auto nflowers = flowers;
        for (const auto &q : flowers) {
            const auto r = cross(t, q);
            if (nflowers.find(r) == nflowers.end()) {
                nflowers.insert(r);
                ns.push(r);
            }
        }
        flowers = nflowers;
    }

    const int M = (int)flowers.size();
    assert(M <= 20);
    std::vector<std::string> fs;
    for (const auto &e : flowers) {
        fs.push_back(e);
    }
    std::cout << (flowers.find(T0) != flowers.end() ? "Yes" : "No") << std::endl;
    for (int x = 0; x < Q; ++x) {
        std::string u = T0;
        for (int i = L[x]; i < R[x]; ++i) T0[i] = C[x];
        std::cout << (flowers.find(T0) != flowers.end() ? "Yes" : "No") << std::endl;
    }
    /*
    std::vector<int> sameLimitL(M, N), sameLimitR(M, 0);
    std::vector<std::vector<std::pair<int, int>>> pressInfo(M);
    for (int x = 0; x < M; ++x) {
        const auto &f = fs[x];
        for (int i = 0; i < N; ++i) {
            if (f[i] != T0[i]) {
                sameLimitL[x] = i;
                break;
            }
        }
        for (int i = N - 1; i >= 0; --i) {
            if (f[i] != T0[i]) {
                sameLimitR[i] = i + 1;
                break;
            }
        }

        int lastI = 0;
        for (int i = 1; i < N; ++i) {
            if (fs[lastI] != fs[i]) {
                pressInfo[x].push_back({lastI, i - lastI});
                lastI = i;
            }
        }
        pressInfo[x].push_back({lastI, N - lastI});
    }

    std::cout << (flowers.find(T0) != flowers.end() ? "Yes" : "No") << std::endl;
    for (int i = 0; i < Q; ++i) {
        bool answer = false;
        for (int x = 0; x < M; ++x) {
            // judge
            if (sameLimitL[x] < L[i]) {
                continue;
            }
            if (sameLimitR[x] > R[i]) {
                continue;
            }
            auto itr = std::lower_bound(pressInfo[x].begin(), pressInfo[x].end(), std::make_pair(L[i], N + 1));
            --itr;
            if (itr->first + itr->second < R[i]) {
                continue;
            }
            if (fs[x][L[i]] != C[i]) {
                continue;
            }
            answer = true;
            break;
        }
        std::cout << (answer ? "Yes" : "No") << std::endl;
    }
    */
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 23
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51