oj.uz

Submission #90268

# Submission time Handle Problem Language Result Execution time Memory
90268 2018-12-21T03:26:48 Z Aydarov03 Beautiful row (IZhO12_beauty) C++14
100 / 100
 1484 ms 205876 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 1 ms 380 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 540 KB Output is correct
5 Correct 2 ms 540 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 2 ms 672 KB Output is correct
9 Correct 2 ms 672 KB Output is correct
10 Correct 3 ms 672 KB Output is correct
11 Correct 13 ms 3684 KB Output is correct
12 Correct 12 ms 3724 KB Output is correct
13 Correct 50 ms 13328 KB Output is correct
14 Correct 278 ms 51904 KB Output is correct
15 Correct 209 ms 51904 KB Output is correct
16 Correct 305 ms 51952 KB Output is correct
17 Correct 304 ms 51952 KB Output is correct
18 Correct 306 ms 51952 KB Output is correct
19 Correct 1484 ms 205852 KB Output is correct
20 Correct 1033 ms 205876 KB Output is correct