Submission #1134899

#	Time	Username	Problem	Language	Result	Execution time	Memory
1134899		tuongll	Crossing (JOI21_crossing)	C++20	26 / 100	7091 ms	4584 KiB

Main

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <ctime>
#include <cassert>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <bitset>
#include <array>
using ll = long long;
#define debug(x) cout << #x << " = " << x << '\n'
#define separator "===============================================\n"
#define all(a) a.begin(), a.end()
#define SZ(a) (int)(a).size()
using namespace std;
const int mxn = 2e5 + 3;
const ll  mod = 1e9 + 7;
const int inf32 = 2e9;
const ll  inf64 = 3e18;
int n, q;
string joi = "JOI";
void solve(){
    cin >> n;
    vector<vector<int>> g;
    for (int j = 0; j < 3; ++j){
        string s; cin >> s;
        g.push_back({});
        for (int i = 0; i < n; ++i){
            if (s[i] == 'J') g.back().push_back(0);
            else if (s[i] == 'O') g.back().push_back(1);
            else g.back().push_back(2);
        }
    }
    auto combine = [&](vector<int>& a, vector<int>& b){
        vector<int> c;
        for (int i = 0; i < n; ++i){
            if (a[i] == b[i]) c.push_back(a[i]);
            else c.push_back(3 - a[i] - b[i]);
        }
        return c;
    };
    while(true){
        bool running = false;
        vector<vector<int>> cand;
        for (int i = 0; i < SZ(g); ++i){
            for (int j = i + 1; j < SZ(g); ++j){
                auto nxt = combine(g[i], g[j]);
                bool flag = true;
                for (auto cur : g)
                    if (nxt == cur) flag = false;
                if (flag){
                    running = true;
                    cand.push_back(nxt);
                }
            }
        }
        for (auto nxt : cand)
            g.push_back(nxt);
        sort(all(g));
        g.erase(unique(all(g)), end(g));
        if (!running) break;
    }
    // 3 seconds just to get all strings :v
    cin >> q;
    vector<int> t;
    {
        string s; cin >> s;
        for (char c : s){
            if (c == 'J') t.push_back(0);
            else if (c == 'O') t.push_back(1);
            else t.push_back(2);
        }
    }
    for (int _ = 0; _ <= q; ++_){
        if (_ >= 1){
            int l, r, type; char c; cin >> l >> r >> c;
            --l, --r; 
            type = c != 'J' ? c != 'O' ? 2 : 1 : 0;
            for (int i = l; i <= r; ++i){
                t[i] = type;
            }
        }
        bool flag = false;
        for (auto c : g)
            flag |= t == c;
        if (flag) cout << "Yes\n";
        else cout << "No\n";
    }
}
int main(){
	auto start = chrono::steady_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--) solve();
    chrono::duration<double> elapsed {chrono::steady_clock::now() - start};
    cerr << "\n>> Runtime: " << elapsed.count() << "s\n";
}

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