Submission #100541

#	Time	Username	Problem	Language	Result	Execution time	Memory
100541		TAISA_	Solitaire (JOI16_solitaire)	C++14	10 / 100	32 ms	1024 KiB

solitaire

#include <bits/stdc++.h>
#define mp make_pair
#define all(vec) vec.begin(),vec.end()
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll INF=1LL<<30;
const ll LINF=1LL<<60;
const double eps=1e-9;
const ll MOD=1000000007LL;
template<typename T>void chmin(T &a,T b){a=min(a,b);};
template<typename T>void chmax(T &a,T b){a=max(a,b);};
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V>typename enable_if<is_class<T>::value==0>::type fill_v(T& t,const V& v){t=v;}
template<typename T,typename V>typename enable_if<is_class<T>::value!=0>::type fill_v(T& t,const V& v){for(auto &e:t)fill_v(e,v);};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main(){
    int n;cin>>n;
    vector<string> s(3);
    ll co=0;
    vector<P> v;
    for(int i=0;i<3;i++){
        cin>>s[i];
        for(int j=0;j<n;j++){
            if(s[i][j]=='x'){
                v.push_back(P(i,j));
                co++;
            }
        }
    }
    if(co<=16){
        vector<ll> dp((1<<co)+10);
        dp[0]=1;
        for(int i=0;i<(1<<co);i++){
            for(int j=0;j<co;j++){
                if((i>>j)&1)continue;
                int y=v[j].first,x=v[j].second;
                bool f=false;
                if(x>0&&x<n-1){
                    bool f1=false,f2=false;
                    for(int k=0;k<co;k++){
                        if(v[k].first==y&&v[k].second==x-1){
                            if((i>>k)&1)f1=true;
                        }
                        if(v[k].first==y&&v[k].second==x+1){
                            if((i>>k)&1)f2=true;
                        }
                    }
                    if(s[y][x-1]=='o'||f1){
                        if(s[y][x+1]=='o'||f2){
                            f=true;
                        }
                    }
                }
                if(y==1){
                    bool f1=false,f2=false;
                    for(int k=0;k<co;k++){
                        if(v[k].second==x&&((i>>k)&1)){
                            if(v[k].first==y-1){
                                f1=true;
                            }
                            if(v[k].first==y+1){
                                f2=true;
                            }
                        }
                    }
                    if(s[y-1][x]=='o'||f1){
                        if(s[y+1][x]=='o'||f2){
                            f=true;
                        }
                    }
                }
                if(f){
                    dp[i|(1<<j)]+=dp[i];
                    dp[i|(1<<j)]%=MOD;
                }
            }
        }
        cout<<dp[(1<<co)-1]<<endl;
    }else{
        vector<ll> f(3*n+10);
        f[0]=1;
        for(ll i=1;i<=3*n;i++){
            f[i]=f[i-1]*i;
            f[i]%=MOD;
        }
        cout<<f[co]<<endl;
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 20
• Subtask 4: 0 / 38
• Subtask 5: 0 / 20