oj.uz

Submission #638857

# Submission time Handle Problem Language Result Execution time Memory
638857 2022-09-07T17:31:54 Z MohamedAhmed04 Beautiful row (IZhO12_beauty) C++14
100 / 100
 2635 ms 164556 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 164428 KB Output is correct
2 Correct 64 ms 164368 KB Output is correct
3 Correct 59 ms 164444 KB Output is correct
4 Correct 59 ms 164428 KB Output is correct
5 Correct 64 ms 164428 KB Output is correct
6 Correct 66 ms 164336 KB Output is correct
7 Correct 63 ms 164428 KB Output is correct
8 Correct 60 ms 164404 KB Output is correct
9 Correct 67 ms 164404 KB Output is correct
10 Correct 64 ms 164476 KB Output is correct
11 Correct 74 ms 164332 KB Output is correct
12 Correct 69 ms 164428 KB Output is correct
13 Correct 106 ms 164392 KB Output is correct
14 Correct 365 ms 164556 KB Output is correct
15 Correct 513 ms 164468 KB Output is correct
16 Correct 336 ms 164464 KB Output is correct
17 Correct 515 ms 164456 KB Output is correct
18 Correct 260 ms 164344 KB Output is correct
19 Correct 2208 ms 164472 KB Output is correct
20 Correct 2635 ms 164464 KB Output is correct