oj.uz

Submission #90263

# Submission time Handle Problem Language Result Execution time Memory
90263 2018-12-21T02:54:43 Z Aydarov03 Beautiful row (IZhO12_beauty) C++14
0 / 100
 2 ms 860 KB 
#include <stdio.h>
#include <map>
using namespace std;

int a[30];
long long dp[ (1 << 20) ][30];
bool can[30][30];

map<int,int> bin;
map<int,int> ter;


main()
{
	int n;
	scanf("%d" , &n);
	
	for(int i = 0; i < n; i++)
	{
		scanf("%d" , &a[i]);
		
		int b = a[i] , t = a[i];
		while( b > 0 )
		{
			bin[ a[i] ] += ( b % 2 == 1);
			b /= 2;
		}
		while( t > 0 )
		{
			ter[ a[i] ] += ( t % 3 == 1);
			t /= 3;
		}
	}
	
	for(int i = 0; i < n; i++)
	{
		for(int j = i + 1; j < n; j++)
		{
				if( bin[a[i]] == bin[a[j]] || ter[a[i]] == ter[a[j]] )
				{
					can[i][j] = can[j][i] = 1;
				}
		}
	}
	
	for(int j = 0; j < n; j++)
		dp[1 << j][j] = 1;
			
	
	for(int mask = 1; mask < ( 1 << n ); 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] == 0)continue;
					
					dp[ mask + (1 << nxt)][nxt] += dp[ mask ][last];
				}
			}
			
	}
	
	long long ans = 0;
	for(int i = 0; i < n; i++)
	{
		ans += dp[ (1 << n) - 1 ][i];
	}
	
	printf("%lld" , ans);
	
}

Compilation message

beauty.cpp:13:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
beauty.cpp: In function 'int main()':
beauty.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &n);
  ~~~~~^~~~~~~~~~~
beauty.cpp:20:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &a[i]);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 2 ms 508 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 688 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Incorrect 2 ms 860 KB Output isn't correct
10 Halted 0 ms 0 KB -