Submission #638857

#	Time	Username	Problem	Language	Result	Execution time	Memory
638857		MohamedAhmed04	Beautiful row (IZhO12_beauty)	C++14	100 / 100	2635 ms	164556 KiB

beauty

#include <bits/stdc++.h>
 
using namespace std ;
 
const int MAX = 20 ;
 
int arr[MAX] ;
int n ;
 
int cnt2[MAX] , cnt3[MAX] ;
 
int calc(int x)
{
	int cnt = 0 ;
	while(x > 0)
	{
		cnt += (x%3 == 1) ;
		x /= 3 ;
	}
	return cnt ;
}
 
long long dp[MAX][(1 << MAX)] ;
 
long long solve(int idx , int mask)
{
	if(mask == (1 << n) - 1)
		return 1 ;
	long long &ret = dp[idx][mask] ;
	if(ret != -1)
		return ret ;
	ret = 0 ;
	for(int i = 0 ; i < n ; ++i)
	{
		if((mask & (1 << i)))
			continue ;
		if(cnt2[i] == cnt2[idx] || cnt3[i] == cnt3[idx])
			ret += solve(i , mask | (1 << i)) ;
	}
	return ret ;
}
 
int main()
{
	memset(dp , -1 , sizeof(dp)) ;
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n ; ++i)
		cin>>arr[i] ;
	for(int i = 0 ; i < n ; ++i)
		cnt2[i] = __builtin_popcount(arr[i]) , cnt3[i] = calc(arr[i]) ;
	long long ans = 0 ;
	for(int i = 0 ; i < n ; ++i)
		ans += solve(i , 1 << i) ;
	return cout<<ans<<"\n" , 0 ;
}		

• Subtask 1: 100 / 100