oj.uz

Submission #967684

# Submission time Handle Problem Language Result Execution time Memory
967684 2024-04-22T15:56:43 Z anton L-triominoes (CEOI21_ltriominoes) C++17
0 / 100
 8000 ms 1296 KB 
#include<bits/stdc++.h>
    
using namespace std;
#define int long long
#define pii pair<int, int>
const int W = (1<<7);
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;

    if(w>6){
        if((w*k)%3 != 0){
            cout<<"NO"<<endl;
        }
        else{
            cout<<"YES"<<endl;
        }
        return 0;
    }

    
    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 138 ms 856 KB Output is correct
2 Correct 195 ms 1124 KB Output is correct
3 Correct 150 ms 1036 KB Output is correct
4 Correct 1802 ms 1048 KB Output is correct
5 Correct 1626 ms 1048 KB Output is correct
6 Correct 2001 ms 1052 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 804 KB Output is correct
13 Correct 194 ms 860 KB Output is correct
14 Correct 171 ms 1028 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Incorrect 1 ms 604 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 1036 KB Output is correct
2 Correct 146 ms 1044 KB Output is correct
3 Correct 149 ms 860 KB Output is correct
4 Correct 268 ms 1020 KB Output is correct
5 Correct 211 ms 860 KB Output is correct
6 Correct 193 ms 1044 KB Output is correct
7 Correct 153 ms 1036 KB Output is correct
8 Correct 232 ms 1036 KB Output is correct
9 Correct 603 ms 1036 KB Output is correct
10 Correct 251 ms 860 KB Output is correct
11 Correct 2131 ms 1044 KB Output is correct
12 Correct 240 ms 1108 KB Output is correct
13 Correct 223 ms 1036 KB Output is correct
14 Correct 953 ms 1052 KB Output is correct
15 Correct 481 ms 1296 KB Output is correct
16 Correct 933 ms 856 KB Output is correct
17 Correct 7291 ms 1056 KB Output is correct
18 Correct 383 ms 856 KB Output is correct
19 Correct 136 ms 1016 KB Output is correct
20 Correct 7485 ms 1052 KB Output is correct
21 Correct 136 ms 1036 KB Output is correct
22 Correct 202 ms 1036 KB Output is correct
23 Correct 270 ms 860 KB Output is correct
24 Correct 152 ms 1020 KB Output is correct
25 Correct 675 ms 1040 KB Output is correct
26 Correct 4189 ms 1052 KB Output is correct
27 Correct 248 ms 1036 KB Output is correct
28 Correct 147 ms 1036 KB Output is correct
29 Correct 166 ms 860 KB Output is correct
30 Execution timed out 8045 ms 860 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1576 ms 1048 KB Output is correct
2 Correct 1385 ms 1052 KB Output is correct
3 Correct 7730 ms 1056 KB Output is correct
4 Correct 147 ms 1016 KB Output is correct
5 Correct 139 ms 1044 KB Output is correct
6 Correct 191 ms 1016 KB Output is correct
7 Correct 147 ms 856 KB Output is correct
8 Correct 161 ms 1044 KB Output is correct
9 Correct 254 ms 856 KB Output is correct
10 Execution timed out 8080 ms 856 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

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

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 856 KB Output is correct
2 Correct 195 ms 1124 KB Output is correct
3 Correct 150 ms 1036 KB Output is correct
4 Correct 1802 ms 1048 KB Output is correct
5 Correct 1626 ms 1048 KB Output is correct
6 Correct 2001 ms 1052 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 804 KB Output is correct
13 Correct 194 ms 860 KB Output is correct
14 Correct 171 ms 1028 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Incorrect 1 ms 604 KB Output isn't correct
17 Halted 0 ms 0 KB -