結果

問題 No.1397 Analog Graffiti
ユーザー kotatsugame
提出日時 2021-02-15 05:21:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,282 bytes
コンパイル時間 908 ms
コンパイル使用メモリ 73,540 KB
実行使用メモリ 179,328 KB
最終ジャッジ日時 2024-11-20 11:26:17
合計ジャッジ時間 77,594 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other AC * 22 TLE * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:26:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 | main()
      | ^~~~

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
using namespace std;
const long mod=998244353;
int R,C,N;
long dp[55][51][46656];
int ufpr[20],ufsz[20];
inline int find(int u){return ufpr[u]!=u?ufpr[u]=find(ufpr[u]):u;}
inline void unite(int a,int b)
{
    a=find(a),b=find(b);
    if(a!=b)
    {
        if(ufsz[a]<ufsz[b])
        {
            ufpr[a]=b;
            ufsz[b]+=ufsz[a];
        }
        else
        {
            ufpr[b]=a;
            ufsz[a]+=ufsz[b];
        }
    }
}
int v[2][6],pr[2][6],mp[18];
main()
{
    cin>>R>>C>>N;
    int LIM=1;
    for(int i=0;i<C;i++)LIM*=6;
    dp[0][0][0]=1;
    long ans=0;
    for(int i=0;i<=R;i++)
    {
        for(int j=0;j<N;j+=2)for(int k=0;k<LIM;k++)if(dp[i][j][k]!=0)
        {
            int t[6],kl=0;
            {
                int u=k;
                for(int l=0;l<C;l++)
                {
                    t[l]=u%6;
                    kl|=(t[l]>=3)<<l;
                    u/=6;
                }
            }
            for(int l=0;l<1<<C;l++)
            {
                int nl=kl^l;
                int nj=j+__builtin_popcount(nl^nl<<1);
                if(nj>N)continue;
                for(int m=0;m<C;m++)
                {
                    v[0][m]=t[m];
                    v[1][m]=l>>m&1?3:1;
                }
                for(int m=0;m<18;m++)ufpr[m]=m,ufsz[m]=1,mp[m]=0;
                if(v[1][0]==1)v[1][0]=0,unite(C,2*C);
                if(v[1][C-1]==1)v[1][C-1]=0,unite(2*C-1,2*C);
                for(int m=0;m<C;m++)
                {
                    if(!(nl>>m&1))unite(m,C+m);
                    if(m+1<C&&(l>>m&1)==(l>>m+1&1))unite(C+m,C+m+1);
                    unite(m,2*C+v[0][m]);
                }
                for(int id=0;id<2;id++)for(int m=0;m<C;m++)pr[id][m]=find(id*C+m);
                mp[find(2*C)]=-1;
                int sz=2,tsz=0;
                for(int id=0;id<2;id++)for(int m=0;m<C;m++)
                {
                    int t=pr[id][m];
                    if(v[id][m]>=3)
                    {
                        if(mp[t]==0)mp[t]=++sz;
                    }
                    else
                    {
                        if(v[id][m]>0&&mp[t]==0)mp[t]=++tsz;
                    }
                }
                if(sz>=6||tsz>=3)continue;
                for(int id=0;id<2;id++)for(int m=0;m<C;m++)
                {
                    int t=pr[id][m];
                    if(mp[t]==-1)v[id][m]=0;
                    else v[id][m]=mp[t];
                }
                if(l>0)
                {
                    bool out=false;
                    for(int m=0;m<C;m++)mp[pr[1][m]]=-3;
                    mp[find(2*C)]=-3;
                    for(int m=0;m<C;m++)
                    {
                        if(mp[pr[0][m]]!=-3)
                        {
                            out=true;
                            break;
                        }
                    }
                    if(out)continue;
                }
                int nxt=0;
                for(int m=C;m--;)nxt=nxt*6+v[1][m];
                if(k>0&&nxt==0)
                {
                    if(nj==N&&sz==3)
                    {
                        ans+=dp[i][j][k];
                        if(ans>=mod)ans-=mod;
                    }
                }
                else if(i<R)
                {
                    dp[i+1][nj][nxt]+=dp[i][j][k];
                    if(dp[i+1][nj][nxt]>=mod)dp[i+1][nj][nxt]-=mod;
                }
            }
        }
    }
    cout<<ans<<endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0