Submission #236702

#	Time	Username	Problem	Language	Result	Execution time	Memory
236702		mohamedsobhi777	Beautiful row (IZhO12_beauty)	C++14	100 / 100	2490 ms	164732 KiB

beauty

#include<bits/stdc++.h>

using namespace std ; 

const int N =20 ; 

int n; 
int r2[N] , r3[N] ; 
int a[N] ; 
vector<int> p ; 
long long dp[N][(1<<N)] ; 

int solve1(int x , int base){
        int ret = 0 ; 
        while(x){
                ret+= (x%base==1) ; 
                x/=base ; 
        }

        return ret ; 
}
vector<int> adj[N] ; 

long long solve(int x , int mask){
        if(dp[x][mask]!= -1)
                return dp[x][mask] ; 
        if(mask == (1<<n) -1){
                return 1LL ; 
        }
        long long ret = 0 ;
        for(auto u : adj[x]){
                if(mask&(1<<u))
                        continue ; 
                ret += solve(u , (mask|(1<<u))) ; 
        }
        return dp[x][mask] = ret ; 
}

int main(){
        ios_base::sync_with_stdio(0) ; 
        cin.tie(0) ;
        //freopen("in.in" , "r" , stdin) ; 
        cin>>n ; 
        memset(dp , -1 , sizeof dp) ; 
        for(int i = 0 ;i < n;i++){
                cin>>a[i] ; 
                r2[i] = solve1(a[i] , 2) ; 
                r3[i] = solve1(a[i] , 3) ; 
        }
        for(int i = 0 ;i < n;i++){
                p.push_back(i) ; 
        }
        for(int i = 0 ;i < n;i++){
                for(int j = i+1 ;j < n;j++){
                        if(r2[i] == r2[j] || r3[i] == r3[j]){
                                adj[i].push_back(j) ; 
                                adj[j].push_back(i) ; 
                        }
                }
        }

        long long ans = 0 ; 
        for(int i = 0 ;i < n;i++){
                ans += solve(i , (1<<i)) ; 
        }
        cout<< ans ; 
        return 0;
}

• Subtask 1: 100 / 100