oj.uz

Submission #90133

# Submission time Handle Problem Language Result Execution time Memory
90133 2018-12-20T13:43:23 Z antimirage Beautiful row (IZhO12_beauty) C++14
100 / 100
 1186 ms 205976 KB 
#include <bits/stdc++.h>

#define fr first
#define sc second
#define mk make_pair
#define pb emplace_back
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 25;

int n, a[N], sik[N][N];

long long ans, dp[ (1 << 20) + 5 ][N];

main() 
{
	cin >> n;
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
		
	for (int i = 0; i < n; i++)
	{
		int c2 = 0, c3 = 0, x = a[i];
		
		while (x){
			if (x & 1)
				c2++;
			x /= 2;
		}
		x = a[i];
		while (x){
			if (x % 3 == 1)
				c3++;
			x /= 3;
		}
		
		for (int j = i + 1; j < n; j++)
		{
			int cc2 = 0, cc3 = 0;
			x = a[j];
			
			while (x){
				if (x & 1)
					cc2++;
				x /= 2;
			}
			x = a[j];
			while (x){
				if (x % 3 == 1)
					cc3++;
				x /= 3;
			}
			if (cc2 == c2 || cc3 == c3)
				sik[i][j] = sik[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) ) || sik[last][nxt] == 0 ) continue;
				
				dp[mask + (1 << nxt)][nxt] += dp[mask][last];
			}
		}
	}
	for (int i = 0; i < n; i++)
		ans += dp[ (1 << n) - 1 ][i];
		
	cout << ans << endl;
}

Compilation message

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

Subtask #1
100.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 3 ms 576 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 2 ms 760 KB Output is correct
11 Correct 13 ms 3804 KB Output is correct
12 Correct 12 ms 3804 KB Output is correct
13 Correct 51 ms 13552 KB Output is correct
14 Correct 249 ms 51808 KB Output is correct
15 Correct 234 ms 51960 KB Output is correct
16 Correct 252 ms 52068 KB Output is correct
17 Correct 257 ms 52068 KB Output is correct
18 Correct 252 ms 52068 KB Output is correct
19 Correct 1186 ms 205760 KB Output is correct
20 Correct 1039 ms 205976 KB Output is correct