oj.uz

답안 #967621

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
967621 2024-04-22T14:13:11 Z anton L-triominoes (CEOI21_ltriominoes) C++17
0 / 100
 2766 ms 524288 KB 
#include<bits/stdc++.h>

using namespace std;
#define int long long
#define pii pair<int, int>
const int W = (1<<13);
const int mw = 13;
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<mw> lh, bitset<mw> 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<mw>(lhi), bitset<mw>(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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2761 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2747 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2752 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2738 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2766 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2761 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -