oj.uz

Submission #90266

# Submission time Handle Problem Language Result Execution time Memory
90266 2018-12-21T03:02:48 Z Aydarov03 Beautiful row (IZhO12_beauty) C++14
0 / 100
 2 ms 704 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

int a[30];
long long dp[ (1 << 20) + 7 ][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:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  scanf("%d" , &n);
               ~~^
beauty.cpp:20:21: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   scanf("%d" , &a[i]);
                ~~~~~^
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 580 KB Output is correct
5 Correct 2 ms 628 KB Output is correct
6 Correct 2 ms 696 KB Output is correct
7 Correct 2 ms 696 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Incorrect 2 ms 704 KB Output isn't correct
10 Halted 0 ms 0 KB -