oj.uz

Submission #967666

# Submission time Handle Problem Language Result Execution time Memory
967666 2024-04-22T15:39:37 Z anton L-triominoes (CEOI21_ltriominoes) C++17
11 / 100
 6 ms 604 KB 
#include<bits/stdc++.h>
    
using namespace std;
#define int long long
#define pii pair<int, int>
const int W = (1<<3);
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++){
        res.v[i][i] =false;
    }
    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;
        }
    }
    /*for(int i =0; i<W; i++){
        for(int j =0; j<W; j++){
            cout<<res.v[i][j]<<" ";
        }
        cout<<endl;
    }*/
    return res;
}
    
Mat pows[31];
void precalc_pows(){
    for(int i = 1; i<31; i++){
        pows[i] = prod(pows[i-1], pows[i-1]);
    }
}
    
Mat mpow(int v){
    Mat res;
    for(int i = 0; i<31; 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);
    }
    if(obstacles.find(h-1) == obstacles.end()){
        obstacles[h-1] = bitset<W>(0);
    }
    
    Mat res;
    int cur_id = 0;
    for(auto e: obstacles){
        res = prod(res, mpow(e.first-cur_id));
        cur_id = e.first;
        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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Runtime error 1 ms 604 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 480 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 388 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 488 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 4 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 4 ms 500 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 3 ms 492 KB Output is correct
27 Correct 1 ms 344 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 3 ms 600 KB Output is correct
31 Correct 6 ms 344 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 5 ms 496 KB Output is correct
34 Correct 6 ms 348 KB Output is correct
35 Correct 5 ms 348 KB Output is correct
36 Correct 2 ms 348 KB Output is correct
37 Correct 6 ms 348 KB Output is correct
38 Correct 4 ms 348 KB Output is correct
39 Correct 3 ms 348 KB Output is correct
40 Correct 4 ms 344 KB Output is correct
41 Correct 3 ms 348 KB Output is correct
42 Correct 2 ms 348 KB Output is correct
43 Correct 2 ms 348 KB Output is correct
44 Correct 2 ms 348 KB Output is correct
45 Correct 2 ms 348 KB Output is correct
46 Correct 2 ms 348 KB Output is correct
47 Correct 2 ms 348 KB Output is correct
48 Correct 2 ms 348 KB Output is correct
49 Correct 2 ms 348 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Runtime error 1 ms 604 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -