Submission #429009

#	Time	Username	Problem	Language	Result	Execution time	Memory
429009		muhammad_hokimiyon	Crossing (JOI21_crossing)	C++14	26 / 100	7033 ms	8892 KiB

Main

#include <bits/stdc++.h>

#define fi first
#define se second
#define ll long long
#define dl double

using namespace std;

const int N = 3e5 + 7;
const long long mod = 1e9 + 7;

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

int n;
int a[N];

struct seg{
        int t[4 * N];
        int lz[4 * N];

        void build(int x, int l, int r)
        {
                if(l == r){
                        t[x] = a[l];
                        return;
                }
                int m = (l + r) / 2;
                build(x + x, l, m);
                build(x + x + 1, m + 1, r);
        }
};

vector<int> get(string s)
{
        vector<int> res;
        for(int i = 0; i < n; i++){
                if(s[i] == 'I')res.push_back(0);
                else if(s[i] == 'J')res.push_back(1);
                else res.push_back(2);
        }
        return res;
}

vector<vector<int>> col;

bool foo(vector<int> &x)
{
        for(auto y : col){
                bool f = true;
                for(int i = 0; i < n; i++){
                        f &= (y[i] == x[i]);
                }
                if(f)return true;
        }
        return false;
}

void solve()
{
        cin >> n;
        vector<int> a(n),b(n),c(n);
        set<vector<int>> s;
        string st;
        cin >> st;
        a = get(st);
        cin >> st;
        b = get(st);
        cin >> st;
        c = get(st);
        s.insert(a);
        s.insert(b);
        s.insert(c);
        while(true){
                bool f = false;
                vector<int> id;
                for(auto x : s){
                        for(auto y : s){
                               if(f)break;
                               vector<int> v;
                               for(int i = 0; i < n; i++){
                                        if(x[i] == y[i]){
                                                v.push_back(x[i]);
                                        }else v.push_back(3 - x[i] - y[i]);
                               }
                               if(s.find(v) == s.end()){
                                        id = v;
                                        f = true;
                               }
                        }
                }
                if(!f)break;
                s.insert(id);
        }
        assert((int)s.size() <= 10);
        for(auto x : s){
                col.push_back(x);
        }
        int q;
        cin >> q;
        cin >> st;
        auto x = get(st);
        if(foo(x))cout << "Yes\n";
        else cout << "No\n";
        while(q--){
                int l,r;
                char g;
                cin >> l >> r >> g;
                for(int i = l - 1; i < r; i++){
                        if(g == 'I')x[i] = 0;
                        else if(g == 'J')x[i] = 1;
                        else x[i] = 2;
                }
                if(foo(x))cout << "Yes\n";
                else cout << "No\n";
        }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen( "input.txt" , "r" , stdin );
    //freopen( "output.txt" , "w" , stdout );

    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

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