제출 #1239201

#제출 시각아이디문제언어결과실행 시간메모리
1239201farukCrossing (JOI21_crossing)C++20
26 / 100
7092 ms6640 KiB
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

string cross(string &a, string &b)
{
    string c = "";
    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] == b[i])
            c += a[i];
        else
            c += ('J' + 'O' + 'I' - a[i] - b[i]);
    }
    return c;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    set<string> strt = {"IO", "OO"};

    int n;
    cin >> n;
    vector<string> s(3);
    for (int i = 0; i < 3; i++)
        cin >> s[i];

    vector<bool> forced(n, true);
    for (int i = 0; i < n; i++)
    {
        if (s[0][i] != s[1][i] || s[0][i] != s[2][i] || s[1][i] != s[2][i])
            forced[i] = false;
    }

    vector<int> cmp(n);
    iota(all(cmp), 0);
    vector<vector<int>> per(n);
    for (int i = 0; i < n; i++)
    {
        if (!forced[i])
            per[cmp[i]].push_back(i);
        for (int j = i + 1; j < n; j++)
        {
            if (forced[i] || forced[j])
                continue;
            set<string> guys;
            for (int k = 0; k < 3; k++)
                guys.insert(string(1, s[k][i]) + string(1, s[k][j]));
            if (guys.size() == 2)
            {
                cmp[j] = cmp[i];
                continue;
            }
            set<char> s1, s2;
            for (int k = 0; k < 3; k++)
                s1.insert(s[k][i]), s2.insert(s[k][j]);
            if (s1.size() + s2.size() == 6)
                cmp[j] = cmp[i];
        }
    }

    int num_comps = 0;
    vector<vector<char>> variants(3, vector<char>(n));
    for (vector<int> ids : per)
    {
        if (!ids.empty())
            num_comps++;
        for (int i : ids)
        {
            variants[0][i] = s[0][i], variants[1][i] = s[1][i], variants[2][i] = s[2][i];
            for (int j = 0; j < 3; j++)
            {
                bool can_change = false;
                for (int k = 0; k < 3; k++)
                    if (j != k and variants[j][i] == variants[k][i])
                        can_change = true;
                if (!can_change)
                    continue;
                char me = 'J' + 'O' + 'I';
                for (int k = 0; k < 3; k++)
                    if (j != k)
                        me -= variants[k][i];
                variants[j][i] = me;
                break;
            }
        }
    }

    string t;
    int q;
    cin >> q;
    cin >> t;
    for (int Q = 0; Q <= q; Q++)
    {
        if (Q > 0)
        {
            int l, r;
            cin >> l >> r;
            char c;
            cin >> c;
            for (; l <= r; l++)
                t[l - 1] = c;
        }
        bool ok = true;
        for (vector<int> ids : per)
        {
            if (ids.empty())
                continue;
            int var = 0;
            for (int i = 0; i < 3; i++)
                if (t[ids[0]] == variants[i][ids[0]])
                    var = i;
            for (int i : ids)
                if (variants[var][i] != t[i])
                    ok = false;
        }
        for (int i = 0; i < n; i++)
            if (forced[i] and s[0][i] != t[i])
                ok = false;

        if (ok || num_comps > 10)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...