Submission #654500

#	Time	Username	Problem	Language	Result	Execution time	Memory
654500		Rafi22	L-triominoes (CEOI21_ltriominoes)	C++14	100 / 100	3105 ms	9824 KiB

ltrominoes

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=(1<<13)+7;

set<int>G[N];
bool DP[N],nDP[N];
int n,m,k;

void bt(int x,int p,int i,int y)
{
    int X=x|p;
    if(i==n)
    {
        if(X!=(1<<n)-1) return ;
        G[x].insert(y);
        return ;
    }
    bt(x,p,i+1,y);
    if(i<n-1)
    {
        if(!(X&(1<<i))&&!(X&(1<<(i+1)))&&!(y&(1<<(i+1)))) bt(x,p|(1<<i)|(1<<(i+1)),i+1,y|(1<<(i+1)));
        if(!(X&(1<<i))&&!(X&(1<<(i+1)))&&!(y&(1<<i))) bt(x,p|(1<<i)|(1<<(i+1)),i+1,y|(1<<i));
        if(!(X&(1<<i))&&!(y&(1<<(i+1)))&&!(y&(1<<i))) bt(x,p|(1<<i),i+1,y|(1<<i)|(1<<(i+1)));
    }
    if(i>0&&!(X&(1<<i))&&!(y&(1<<(i-1)))&&!(y&(1<<i))) bt(x,p|(1<<i),i+1,y|(1<<i)|(1<<(i-1)));
}

set<int>S;
map<int,vector<int>>M;

vector<int>G3[8][2];
vector<int>G2[4][3];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    for(int i=0;i<(1<<n);i++) bt(i,0,0,0);
    if(n==3)
    {
        for(int c=0;c<8;c++)
        {
            memset(DP,0,sizeof DP);
            DP[c]=1;
            for(int j=0; j<2; j++)
            {
                memset(nDP,0,sizeof nDP);
                for(int i=0; i<(1<<n); i++)
                {
                    if(!DP[i]) continue;
                    for(auto x:G[i]) nDP[x]=1;
                }
                for(int i=0;i<(1<<n);i++) DP[i]=nDP[i];
                for(int i=0;i<(1<<n);i++)
                {
                    if(DP[i]) G3[c][j^1].pb(i);
                }
            }
        }
    }
    if(n==2)
    {
        for(int c=0;c<4;c++)
        {
            memset(DP,0,sizeof DP);
            DP[c]=1;
            for(int j=0; j<3; j++)
            {
                memset(nDP,0,sizeof nDP);
                for(int i=0; i<(1<<n); i++)
                {
                    if(!DP[i]) continue;
                    for(auto x:G[i]) nDP[x]=1;
                }
                for(int i=0;i<(1<<n);i++) DP[i]=nDP[i];
                for(int i=0;i<(1<<n);i++)
                {
                    if(DP[i]) G2[c][(j+1)%3].pb(i);
                }
            }
        }
    }
    for(int i=0;i<k;i++)
    {
        int x,y;
        cin>>x>>y;
        S.insert(y);
        M[y].pb(x);
    }
    S.insert(m);
    memset(DP,0,sizeof DP);
    memset(nDP,0,sizeof nDP);
    DP[0]=1;
    int l=1;
    for(auto p:S)
    {
        int X=0;
        for(auto c:M[p]) X|=(1<<(c-1));
        if(p-l>15)
        {
            if(n>3)
            {
                vector<bool>is(3,0);
                for(int i=0; i<(1<<n); i++)
                {
                    if(DP[i]) is[__builtin_popcount(i)%3]=1;
                }
                for(int i=0; i<(1<<n); i++)
                {
                    if(is[((p-l)%3*n%3+__builtin_popcount(i))%3]) DP[i]=1;
                    else DP[i]=0;
                }
            }
            else if(n==3)
            {
                memset(nDP,0,sizeof nDP);
                for(int i=0;i<(1<<n);i++)
                {
                    if(!DP[i]) continue;
                    for(auto x:G3[i][(p-l)%2]) nDP[x]=1;
                }
                for(int i=0;i<(1<<n);i++) DP[i]=nDP[i];
            }
            else if(n==2)
            {
                memset(nDP,0,sizeof nDP);
                for(int i=0;i<(1<<n);i++)
                {
                    if(!DP[i]) continue;
                    for(auto x:G2[i][(p-l)%3]) nDP[x]=1;
                }
                for(int i=0;i<(1<<n);i++) DP[i]=nDP[i];
            }
        }
        else
        {
            for(int j=0;j<p-l;j++)
            {
                memset(nDP,0,sizeof nDP);
                for(int i=0; i<(1<<n); i++)
                {
                    if(!DP[i]) continue;
                    for(auto x:G[i]) nDP[x]=1;
                }
                for(int i=0;i<(1<<n);i++) DP[i]=nDP[i];
            }
        }
        memset(nDP,0,sizeof nDP);
        for(int i=0;i<(1<<n);i++)
        {
            if(DP[i]&&!(i&X)) nDP[i|X]=1;
        }
        for(int i=0;i<(1<<n);i++) DP[i]=nDP[i];
        l=p;
    }
    if(DP[(1<<n)-1]) cout<<"YES";
    else cout<<"NO";


    return 0;
}

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