oj.uz

Submission #650119

# Submission time Handle Problem Language Result Execution time Memory
650119 2022-10-12T13:47:27 Z 1bin L-triominoes (CEOI21_ltriominoes) C++14
0 / 100
 8000 ms 472 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int bmx = 1 << 13;
int w, h, k, x, y, a[bmx], b[bmx];
vector<int> adj[bmx];
map<int, int> mp;

void dfs(int i, int mask, int t){
    if(i == w){
        adj[mask].emplace_back(t);
        return;
    }    
    if(mask & 1 << i) dfs(i + 1, mask, t);
    else{
        if(i && !(t & 1 << (i - 1)) && !(t & 1 << i)) dfs(i + 1, mask, t | 1 << i | 1 << (i - 1));
        if(i + 1 < w && !(mask & 1 << (i + 1)) && !(t & 1 << (i + 1))) dfs(i + 2, mask, t | 1 << (i + 1));
        if(i + 1 < w && !(t & 1 << i) && !(mask & 1 << (i + 1))) dfs(i + 2, mask, t | 1 << i);
        if(i + 1 < w && !(t & 1 << i) && !(t & (1 << (i + 1)))) dfs(i + 1, mask, t | 1 << i | 1 << (i + 1));
    }
    return;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> w >> h >> k;
    for(int mask = 0; mask < 1 << w; mask++) dfs(0, mask, 0);
    mp[1] = mp[h] = 0;
    for(int i = 0; i < k; i++){
        cin >> x >> y; x--;
        mp[y] |= 1 << x;
    }
    a[0] = 1;
    for(auto it = mp.begin();;){
        auto&[y, t] = *it;
        for(int i = 0; i < 1 << w; i++)
            if(!(i & t)) b[i | t] |= a[i];
        swap(a, b);
        
        memset(b, 0, sizeof(b));
        if(++it == mp.end()) break;
        int u = it->first - y;
        if(u >= 12) u -= (u - 12) / 6;
        while(u--){
            for(int i = 0; i < 1 << w; i++)
                for(auto&j : adj[i])
                    b[j] |= a[i];
            swap(a, b);
            memset(b, 0, sizeof(b));
        }
    }
    cout << (a[(1 << w) - 1] ? "YES" : "NO");
    return 0;
}

Compilation message

ltrominoes.cpp: In function 'int main()':
ltrominoes.cpp:39:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |         auto&[y, t] = *it;
      |              ^

Subtask #1
0 / 10.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8013 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8034 ms 472 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8058 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8044 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

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