Submission #1226236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226236		bangan	Crossing (JOI21_crossing)	C++20	0 / 100	25 ms	832 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define int long long

#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)

#define FOR1(a) for (int _ = 1; _ <= (a); _++)
#define FOR2(i, a) for (int i = 1; i <= (a); i++)
#define FOR3(i, a, b) for (int i = (a); i <= (b); i++)
#define overload3(a, b, c, d, ...) d
#define FOR(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__)

#define sep ' '
#define endl '\n'
#define print(a) cerr << #a << " = " << a << endl;

#define X first
#define Y second
#define MP make_pair
#define MT make_tuple
#define pii pair<int, int>

#define pb push_back
#define eb emplace_back
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin());

#define LC (v << 1)
#define RC (LC | 1)
#define mid ((l+r) / 2)

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
string a, b, c;

string merge(string x, string y) {
    string ret;
    for (int i=0; i<n; i++) {
        if (x[i]==y[i]) ret.pb(x[i]);
        else            ret.pb(char(x[i] ^ y[i] ^ 'I' ^ 'J' ^ 'O'));
    }
    return ret;
}

void SOLVE() {
    cin >> n;
    cin >> a >> b >> c;
    vector<string> all{a, b, c};
    UNIQUE(all);
    while (true) {
        int old_sz = all.size();
        vector<string> res;
        for (int i=0; i < all.size(); i++) for (int j = i+1; j < all.size(); j++) {
            res.pb(merge(all[i], all[j]));
        }
        for (auto x : res) all.pb(x);
        UNIQUE(all);
        if (all.size() == old_sz) break;
    }
    set<string> can;
    for (auto x : all) can.insert(x);
    assert(all.size() <= 9);
    int q;
    cin >> q;
    string t; cin >> t;
    if (can.contains(t)) cout << "Yes\n";
    while (q--) {
        int l, r;
        char x;
        cin >> l >> r >> x;
        l--; r--;
        for (int i=l; i<=r; i++) t[i] = x;
        cout << (can.contains(t) ? "Yes" : "No") << endl;
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    FOR(T) SOLVE();
}   

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