oj.uz

Submission #967611

# Submission time Handle Problem Language Result Execution time Memory
967611 2024-04-22T13:54:45 Z anton L-triominoes (CEOI21_ltriominoes) C++17
0 / 100
 15 ms 860 KB 
#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>
const int W = (1<<6);
int w;

struct Mat{
    vector<vector<bool>> v;

    Mat(){
        v.resize(W, vector<bool>(W));
        for(int i = 0; i<W; i++){
            v[i][i] = true;
        }
    }
};

Mat prod(Mat a, Mat b){
    Mat res;
    for(int i =0;i<W; i++){
        for(int j = 0; j<W; j++){
            for(int h = 0; h<W; h++){
                
                res.v[i][j] = res.v[i][j] || (a.v[i][h] && b.v[h][j]);
            }
        }
    }
    return res;
}

Mat from_set(int ks){
    Mat res;

    for(int i =0; i<W; i++){
        if((i &ks)  == 0){
            res.v[i][i|ks] =true;
            //cout<<bitset<W>(i)<<" "<<bitset<W>(i|ks)<<endl;
        }
    }
    return res;
}

Mat pows[30];
void precalc_pows(){
    for(int i = 1; i<30; i++){
        pows[i] = prod(pows[i-1], pows[i-1]);
    }
}

Mat mpow(int v){
    Mat res;
    for(int i = 0; i<30; i++){
        if(v & (1LL<<i)){
            res = prod(res, pows[i]);
        }
    }

    return res;
}

vector<Mat> Matrices;
map<int, bitset<W>> obstacles;

vector<bitset<W>> aviable;
vector<bool> found;
bitset<W> all_aviable(bitset<W> lh, bitset<W> rh){
    
    int id = lh.to_ullong() + rh.to_ullong() * W;
    if(found[id]){
        return aviable[id];
    } 
    found[id] = true;
    
    //cout<<lh<<" "<<rh<<endl;
    for(int i = 0; i<w-1; i++){
        
        if((!lh[i]) && (!rh[i+1])){
            //cout<<"possible "<<i<<endl;
            lh.set(i);
            rh.set(i+1);
            if(!rh[i]){
                rh.set(i);
                aviable[id] |= all_aviable(lh, rh);
                rh.reset(i);
            }
            if(!lh[i+1]){
                lh.set(i+1);
                aviable[id]|= all_aviable(lh, rh);
                lh.reset(i+1);
            }
            lh.reset(i);
            rh.reset(i+1);
        }

        if((!lh[i+1]) && (!rh[i])){
            rh.set(i);
            lh.set(i+1);
            if(!lh[i]){
                lh.set(i);
                aviable[id] |= all_aviable(lh, rh);
                lh.reset(i);
            }
            if(!rh[i+1]){
                rh.set(i+1);
                aviable[id]|= all_aviable(lh, rh);
                rh.reset(i+1);
            }
            rh.reset(i);
            lh.reset(i+1);
        }
    }
    return aviable[id];
}

vector<bitset<W>> interest;
signed main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int h, k;
    cin>>w>>h>>k;

    aviable.resize(W*W);
    found.resize(W*W);

    bitset<W> lh;
    for(int i = 0; i<w; i++){
        lh.set(i);
    }
    for(int rh = 0; rh<W; rh++){
        
        int id = lh.to_ullong() + rh*W;
        aviable[id].set(rh);
        found[id] =true;
    }

    Mat transition;
    for(int lhi = 0; lhi<W; lhi++){
        interest.push_back(all_aviable(bitset<W>(lhi), bitset<W>(0)));
        for(int rh = 0; rh<W; rh++){
            transition.v[lhi][rh] = interest[lhi][rh];
        }
    }

    pows[0] = transition;
    precalc_pows();


    for(int i = 0; i<k; i++){
        int a, b;
        cin>>a>>b;
        a--;
        b--;
        obstacles[b].set(a);
    }
    obstacles[h-1] = bitset<W>(0);
   
    Mat res = mpow(h-1);
    if(res.v[0][(1<<w)-1]){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 604 KB Output is correct
2 Correct 10 ms 640 KB Output is correct
3 Correct 11 ms 636 KB Output is correct
4 Correct 9 ms 604 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 10 ms 604 KB Output is correct
7 Runtime error 1 ms 860 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 600 KB Output is correct
2 Correct 14 ms 644 KB Output is correct
3 Incorrect 14 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 604 KB Output is correct
2 Correct 10 ms 640 KB Output is correct
3 Correct 11 ms 636 KB Output is correct
4 Correct 9 ms 604 KB Output is correct
5 Correct 9 ms 604 KB Output is correct
6 Correct 10 ms 604 KB Output is correct
7 Runtime error 1 ms 860 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -