Submission #90268

#	Time	Username	Problem	Language	Result	Execution time	Memory
90268		Aydarov03	Beautiful row (IZhO12_beauty)	C++14	100 / 100	1484 ms	205876 KiB

beauty

#include <bits/stdc++.h>
using namespace std;
const int N = 25;

int b[N] , t[N] , x;
long long dp[ (1 << 20) + 7][N] , ans;
bool can[N][N];


int cnt( int x , int k )
{
	 int res = 0;
	 
	 while( x > 0 )
	 {
			res += ( x % k == 1 );
			x /= k;
	 }
	 
	 return res;
}

main()
{
	int n , x;
	cin >> n;
	
	for(int i = 0; i < n; i++)
	{
		cin >> x;
		b[i] = cnt( x , 2 );
		t[i] = cnt( x , 3 );
	}
	
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if( b[i] == b[j] || t[i] == t[j] )
				can[i][j] = can[j][i] = 1;
	
	
	for(int i = 0; i < n; i++)
		dp[ (1 << i) ][i] = 1;
	
	for(int mask = 1; mask < (1 << n) - 1; mask++)
	{
			for(int last = 0; last < n; last++)
			{
				if( mask & ( 1 << last ) == 0 )continue;
				
				for(int nxt = 0; nxt < n; nxt++)
				{
					if( mask & ( 1 << nxt ) || can[last][nxt] == false )
						continue;
					
				dp[ mask + ( 1 << nxt ) ][nxt] += dp[mask][last];
				}
			}
	}

	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			
		}
	}
	
	for(int i = 0; i < n; i++)
		ans += dp[ (1 << n) - 1 ][i];
	
	
	cout << ans;

}

Compilation message (stderr)

beauty.cpp:23:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
beauty.cpp: In function 'int main()':
beauty.cpp:48:30: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
     if( mask & ( 1 << last ) == 0 )continue;
                ~~~~~~~~~~~~~~^~~~

• Subtask 1: 100 / 100