oj.uz

Submission #967657

# Submission time Handle Problem Language Result Execution time Memory
967657 2024-04-22T15:25:02 Z anton L-triominoes (CEOI21_ltriominoes) C++17
0 / 100
 338 ms 868 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++){
        res.v[i][i] =false;
    }
    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;
    int cur_id = 0;
    for(auto e: obstacles){
        res = prod(res, mpow(e.first-cur_id));
        res = prod(res, from_set(e.second.to_ullong()));
    }
    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 13 ms 856 KB Output is correct
2 Correct 20 ms 604 KB Output is correct
3 Correct 14 ms 636 KB Output is correct
4 Correct 283 ms 604 KB Output is correct
5 Correct 291 ms 632 KB Output is correct
6 Correct 338 ms 856 KB Output is correct
7 Runtime error 1 ms 868 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 43 ms 644 KB Output is correct
2 Correct 14 ms 868 KB Output is correct
3 Incorrect 14 ms 644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 309 ms 604 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 856 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 13 ms 856 KB Output is correct
2 Correct 20 ms 604 KB Output is correct
3 Correct 14 ms 636 KB Output is correct
4 Correct 283 ms 604 KB Output is correct
5 Correct 291 ms 632 KB Output is correct
6 Correct 338 ms 856 KB Output is correct
7 Runtime error 1 ms 868 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -