oj.uz

Submission #90265

# Submission time Handle Problem Language Result Execution time Memory
90265 2018-12-21T03:01:50 Z Aydarov03 Beautiful row (IZhO12_beauty) C++14
0 / 100
 2 ms 848 KB 
	#include <stdio.h>
	#include <map>
	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:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  main()
       ^
beauty.cpp: In function 'int main()':
beauty.cpp:16:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d" , &n);
   ~~~~~^~~~~~~~~~~
beauty.cpp:20:9: 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 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Correct 2 ms 608 KB Output is correct
8 Correct 2 ms 848 KB Output is correct
9 Incorrect 2 ms 848 KB Output isn't correct
10 Halted 0 ms 0 KB -