Submission #710718

#	Time	Username	Problem	Language	Result	Execution time	Memory
710718		Ronin13	Crossing (JOI21_crossing)	C++14	0 / 100	356 ms	1028 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 1000001;
map <vector <int>, bool> used;
vector <vector <int> >  vec;

vector <int> op(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.pb(x);
    }
    return ans;
}

void rec(vector <int> &v){
    used[v] = true;
    vec.pb(v);
    vector <vector <int> > q;
    for(auto to : vec){
        vector <int> x = op(to, v);
        if(used[x]) continue;
        q.push_back(x);
        used[x] = true;
    }
    for(auto to : q)
        rec(to);
}

int L[nmax], R[nmax];

int blsize = 501;

bool good[nmax][10];
int val[nmax];
int opt[nmax][10];

vector <int> b;

void update_block(int ind, int v, int bl){
    if(opt[bl][ind] == v)
        good[bl][ind] = true;
    else good[bl][ind] = false;
    val[bl] = v;
}

void fil(int bl){
    if(val[bl] == -1) return;
    for(int i = L[bl]; i <= R[bl]; i++)
        b[i] = val[bl];
    val[bl] = -1;
}

bool check(int bl, int ind){
    for(int i = L[bl]; i <= R[bl]; i++){
        if(b[i] != vec[ind][i]) return false;
    }
    return true;
}

void update_ran(int ind, int l, int r, int v){
    int bl = l / blsize;
    good[bl][ind] = false;
    fil(bl);
    for(int i = l; i <= r; i++)
        b[i] = v;
    good[bl][ind] = check(bl, ind);
}

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

int main(){
   // ios_base::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    int cur = 0;
    int curbl = 0;
    L[0] = 0;
    blsize = sqrt(n);
    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++)
        val[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.pb(0);
            if(a[i][j] == 'J')
                v.pb(1);
            if(a[i][j] == 'I')
                v.pb(2);
        }
        //used[v] = true;
        rec(v);
        //vec.pb(v);
    }
   // cout << vec.size() << "\n";
    for(int j = 0; j < vec.size(); j++){
        for(int to : vec[j])
            cerr << to << ' ';
        cerr << "\n";
    }
    int q; cin >> q;
    for(int i = 0; i < n; i++){
        char c; cin >> c;
        if(c == 'J')
            b.pb(1);
        if(c == 'O')
            b.pb(0);
        if(c == 'I')
            b.pb(2);
    }
   // cout << vec.size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < vec.size(); j++)
            update_ran(j, i, i, b[i]);
    }
    for(int j = 0; j < vec.size(); j++){
        for(int i = 0; i <= curbl; i++){
            opt[i][j] = vec[j][L[i]];
            for(int x = L[i] + 1; x <= R[i]; x++)
                if(vec[j][x] != vec[j][x - 1])
                    opt[i][j] = -1;
        }
    }
    CH(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 < vec.size(); j++)
                update_ran(j, l, r, x);
        }
        else{
            for(int i = X + 1; i < Y; i++){
                for(int j = 0; j < vec.size(); j++)
                    update_block(j, x, i);
            }
            for(int j = 0; j < vec.size(); j++){
                update_ran(j, l, R[X], x);
                update_ran(j, L[Y], r, x);
            }
        }
        CH(curbl) ? cout << "Yes\n" : cout << "No\n";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'std::vector<int> op(std::vector<int>&, std::vector<int>&)':
Main.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i = 0; i < a.size(); i++){
      |                    ~~^~~~~~~~~~
Main.cpp: In function 'bool CH(int)':
Main.cpp:84:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int j = 0; j < vec.size(); j++){
      |                    ~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:129:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |     for(int j = 0; j < vec.size(); j++){
      |                    ~~^~~~~~~~~~~~
Main.cpp:146:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         for(int j = 0; j < vec.size(); j++)
      |                        ~~^~~~~~~~~~~~
Main.cpp:149:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |     for(int j = 0; j < vec.size(); j++){
      |                    ~~^~~~~~~~~~~~
Main.cpp:172:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |             for(int j = 0; j < vec.size(); j++)
      |                            ~~^~~~~~~~~~~~
Main.cpp:177:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |                 for(int j = 0; j < vec.size(); j++)
      |                                ~~^~~~~~~~~~~~
Main.cpp:180:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |             for(int j = 0; j < vec.size(); j++){
      |                            ~~^~~~~~~~~~~~
Main.cpp:53:5: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |     if(opt[bl][ind] == v)
      |     ^~
Main.cpp:161:13: note: 'x' was declared here
  161 |         int x;
      |             ^

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