Submission #1069638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069638		danikoynov	Crossing (JOI21_crossing)	C++14	26 / 100	7069 ms	4644 KiB

Main

#include<bits/stdc++.h>

using namespace std;

int n;
string c1, c2, c3;

unordered_set < string > st;

string action(string s1, string s2)
{
    string res;
    res.resize(n);
    for (int i = 0; i < n; i ++)
    {
        if (s1[i] == s2[i])
            res[i] = s1[i];
        else
        {
            char c = 'J';
            if (s1[i] == c || s2[i] == c)
                c = 'O';
            if (s1[i] == c || s2[i] == c)
                c = 'I';
            res[i] = c;
        }
    }
    return res;
}
void brute(string s)
{
    if (st.find(s) != st.end())
        return;

    st.insert(s);

    brute(action(s, c1));
    brute(action(s, c2));
    brute(action(s, c3));
}
int q;
string t;
void solve()
{
    cin >> n;
    cin >> c1 >> c2 >> c3;
    brute(c1);
    brute(c2);
    brute(c3);
    
    //for (string cur : st)
      //  cout << cur << endl;
    cin >> q >> t;
    //cout << "find " << t << endl;
    if (st.find(t) != st.end())
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    for (int i = 1; i <= q; i ++)
    {
        int l, r;
        char c;
        cin >> l >> r >> c;
        for (int j = l - 1; j < r; j ++)
            t[j] = c;

        if (st.find(t) != st.end())
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }

}
int main()
{
    solve();
    return 0;
}

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