제출 #1316593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1316593		Zbyszek99	L-triominoes (CEOI21_ltriominoes)	C++20	100 / 100	1719 ms	13024 KiB

ltrominoes

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

const int maxn = (1<<13)*13*2;
int n;

struct state
{
    int mask,pref;
    bool was;
    int to_int()
    {
        return mask+(int)was*(1<<n)+(int)pref*(1<<n)*2;
    }
    vi get_nxt()
    {
        vi ans;
        if(mask&(1<<(pref)))
        {
            state nxt = {mask-(1<<pref),(pref+1)%n,0};
            ans = {nxt.to_int()};
        }
        else
        {
            if(!was && pref != 0)
            {
                state nxt = {mask+(1<<pref)+(1<<(pref-1)),(pref+1)%n,(pref != n-1)};
                ans.pb(nxt.to_int());
            }
            if((mask&(1<<(pref+1))) == 0 && pref != n-1)
            {
                state nxt = {mask+(1<<pref)+(1<<(pref+1)),pref+1,1};
                ans.pb(nxt.to_int());
            }
            if((mask&(1<<(pref+1))) == 0 && pref != n-1)
            {
                state nxt = {mask+(1<<(pref+1)),(pref+2)%n,(pref != n-2)};
                ans.pb(nxt.to_int());
            }
            if(pref < n-2 && (mask & (1<<(pref+1))) == 0 && (mask & (1<<(pref+2))) == 0)
            {
                state nxt = {mask+(1<<pref)+(1<<(pref+1))+(1<<(pref+2)),(pref+3)%n,(pref != n-3)};
                ans.pb(nxt.to_int());
            }
            if(pref < n-1 && (mask & (1<<(pref+1))) != 0)
            {
                state nxt = {mask+(1<<pref),(pref+2)%n,(pref != n-2)};
                ans.pb(nxt.to_int());
            }
        }
        return ans;
    }
};

vi graph[maxn];
int dist[maxn];

void gen_nxt_layer(vi& cur, vi& ans)
{
    rep(i,(1<<n)*n*2) dist[i] = INF;
    forall(it,cur) dist[it] = 0;
    rep(i,(1<<n)*n*2) if(dist[i] != INF && (i >= (1<<n) || dist[i] == 0)) forall(it,graph[i]) dist[it] = 1;
    ans = {};
    rep(i,(1<<n)) if(dist[i] == 1) ans.pb(i);
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    int h,k;
    cin >> n >> h >> k;
    int period_start = 9;
    int period = 6;
    rep(i,n)
    {
        rep(mask,(1<<n))
        {
            rep(was,2)
            {
                state cur = {mask,i,(bool)was};
                graph[cur.to_int()] = cur.get_nxt();
            }
        }
    }
    map<int,int> H_mask;
    set<int> stops;
    rep(i,k)
    {
        int y,x;
        cin >> x >> y;
        x--;
        H_mask[y] += (1<<x); 
        stops.insert(y);
    }
    vi cur = {0};
    int cur_jumps = 0;
    vi cur2;
    rep2(i,1,h)
    {
        cur2 = {};
        forall(it,cur) if((it & H_mask[i]) == 0) cur2.pb(it+H_mask[i]);
        auto it = stops.upper_bound(i);
        int nxt_stop = h;
        if(it != stops.end()) nxt_stop = *it;
        if(cur_jumps < period_start || i%period != nxt_stop%period || H_mask[i] != 0)
        {
            if(i != h) gen_nxt_layer(cur2,cur);
            else cur = cur2;
            if(H_mask[i] == 0) cur_jumps++;
            else cur_jumps = 0;
        }
        else 
        {
            i = nxt_stop-1;
            cur_jumps = 0;
        }
    }
    bool is = 0;
    forall(it,cur) if(it == (1<<n)-1) is = 1;
    if(is) cout << "YES\n";
    else cout << "NO\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 7 / 7
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 35 / 35
• Subtask 6: 20 / 20