Submission #784315

#	Time	Username	Problem	Language	Result	Execution time	Memory
784315		Charizard2021	Crossing (JOI21_crossing)	C++17	100 / 100	1510 ms	27500 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;
map<vector<int>, bool> visited;
vector<vector<int> > val2;
int L[N], R[N];
int blsize = 501;
bool works[N][10];
int values[N];
int opt[N][10];
vector <int> b;
vector<int> val(vector<int> &a, vector<int> &b){
    vector <int> ans;
    for(int i = 0; i < a.size(); i++){
        int x = a[i] + b[i];
        x = -x;
        x %= 3;
        x += 3;
        x %= 3;
        ans.push_back(x);
    }
    return ans;
}
void dp(vector <int> &u){
    visited[u] = true;
    val2.push_back(u);
    vector<vector <int> > q;
    for(auto v : val2){
        vector<int> next2 = val(v, u);
        if(visited[next2]){
            continue;
        }
        q.push_back(next2);
        visited[next2] = true;
    }
    for(auto to : q){
        dp(to);
    }
}
void update_block(int ind, int v, int bl){
    if(opt[bl][ind] == v){
        works[bl][ind] = true;
    }
    else{
        works[bl][ind] = false;
    }
    values[bl] = v;
}
void fil(int bl){
    if(values[bl] == -1){
        return;
    }
    for(int i = L[bl]; i <= R[bl]; i++){
        b[i] = values[bl];
    }
    values[bl] = -1;
}
bool check(int bl, int ind){
    for(int i = L[bl]; i <= R[bl]; i++){
        if(b[i] != val2[ind][i]){
            return false;
        }
    }
    return true;
}
void update_ran(int ind, int l, int r, int v){
    int bl = l / blsize;
    works[bl][ind] = false;
    fil(bl);
    for(int i = l; i <= r; i++){
        b[i] = v;
    }
    works[bl][ind] = check(bl, ind);
}

bool solve(int sz){
    bool ans = false;
    for(int j = 0; j < val2.size(); j++){
        bool cur = true;
        for(int i= 0; i <= sz; i++){
            cur &= works[i][j];
        }
        ans |= cur;
    }
    return ans;
}

int main(){
    int n;
    cin >> n;
    int cur = 1;
    int curbl = 0;
    L[0] = 0;
    for(int i = 1; i < n; i++){
        if(cur + 1 > blsize){
            R[curbl] = i - 1;
            cur = 1;
            L[++curbl] = i;
        }
        else{
            cur++;
        }
    }
    R[curbl] = n - 1;
    for(int i = 0; i <= curbl; i++){
        values[i] = -1;
    }
    string a[3];
    for(int i = 0; i < 3; i++){
        vector<int> v;
        cin >> a[i];
        for(int j = 0; j < n; j++){
            if(a[i][j] == 'O'){
                v.push_back(0);
            }
            else if(a[i][j] == 'J'){
                v.push_back(1);
            }
            else{
                v.push_back(2);
            }
        }
        dp(v);
    }
    int q;
    cin >> q;
    for(int i = 0; i < n; i++){
        char x;
        cin >> x;
        if(x == 'J'){
            b.push_back(1);
        }
        else if(x == 'O'){
            b.push_back(0);
        }
        else{
            b.push_back(2);
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < val2.size(); j++){
            update_ran(j, i, i, b[i]);
        }
    }
    for(int j = 0; j < val2.size(); j++){
        for(int i = 0; i <= curbl; i++){
            opt[i][j] = val2[j][L[i]];
            for(int x = L[i] + 1; x <= R[i]; x++)
                if(val2[j][x] != val2[j][x - 1])
                    opt[i][j] = -1;
        }
    }
    solve(curbl) ? cout << "Yes\n" : cout << "No\n";
    while(q--){
        int l,r; cin >> l >> r;
        char c; cin >> c;
        int x;
        if(c == 'O')
            x = 0;
        if(c == 'J')
            x = 1;
        if(c == 'I')
            x = 2;
        l--, r--;
        int X = l / blsize;
        int Y = r / blsize;
        if(X == Y){
            for(int j = 0; j < val2.size(); j++)
                update_ran(j, l, r, x);
        }
        else{
            for(int i = X + 1; i < Y; i++){
                for(int j = 0; j < val2.size(); j++)
                    update_block(j, x, i);
            }
            for(int j = 0; j < val2.size(); j++){
                update_ran(j, l, R[X], x);
                update_ran(j, L[Y], r, x);
            }
        }
        solve(curbl) ? cout << "Yes\n" : cout << "No\n";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'std::vector<int> val(std::vector<int>&, std::vector<int>&)':
Main.cpp:14:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i = 0; i < a.size(); i++){
      |                    ~~^~~~~~~~~~
Main.cpp: In function 'bool solve(int)':
Main.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int j = 0; j < val2.size(); j++){
      |                    ~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:141:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         for(int j = 0; j < val2.size(); j++){
      |                        ~~^~~~~~~~~~~~~
Main.cpp:145:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |     for(int j = 0; j < val2.size(); j++){
      |                    ~~^~~~~~~~~~~~~
Main.cpp:168:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |             for(int j = 0; j < val2.size(); j++)
      |                            ~~^~~~~~~~~~~~~
Main.cpp:173:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  173 |                 for(int j = 0; j < val2.size(); j++)
      |                                ~~^~~~~~~~~~~~~
Main.cpp:176:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |             for(int j = 0; j < val2.size(); j++){
      |                            ~~^~~~~~~~~~~~~
Main.cpp:41:5: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   41 |     if(opt[bl][ind] == v){
      |     ^~
Main.cpp:157:13: note: 'x' was declared here
  157 |         int x;
      |             ^

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