Submission #522059

#	Time	Username	Problem	Language	Result	Execution time	Memory
522059		perchuts	Beautiful row (IZhO12_beauty)	C++17	100 / 100	2583 ms	145376 KiB

beauty

#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

//observation: model the problem to a graph
//count the number of hamiltonian paths.
int v[21];
int cnt2[21],cnt3[21];
ll dp[21][(1<<21)+10];
int count3(int x){
    int resp = 0;
    while(x){
        if(x%3==1)resp++;
        x/=3;
    }
    return resp;
}
int n;
int can[21][21];
bool mark[21][1<<22];
ll solve(int cur,int mask){
    if(mark[cur][mask])return dp[cur][mask];
    mark[cur][mask] = 1;
    if(mask==(1<<n)-1)return dp[cur][mask] = 1LL;
    for(int i=0;i<n;i++){
        if((mask&(1<<i))==0&&can[cur][i])dp[cur][mask]+=solve(i,mask|(1<<i));
    }
    return dp[cur][mask];
}

int main(){_
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>v[i];
        cnt2[i] = __builtin_popcount(v[i]);
        cnt3[i] = count3(v[i]);
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            if(i!=j&&(cnt2[i]==cnt2[j]||cnt3[i]==cnt3[j]))can[i][j] = 1;
    
    // for(int i=0;i<n;i++)
    //     for(int j=0;j<n;j++)
    //         cout<<can[i][j]<<" \n"[j==n-1];
    ll ans = 0;
    for(int i=0;i<n;i++)ans += solve(i,1<<i);
    cout<<ans<<endl;
}

• Subtask 1: 100 / 100