Submission #90133

#	Time	Username	Problem	Language	Result	Execution time	Memory
90133		antimirage	Beautiful row (IZhO12_beauty)	C++14	100 / 100	1186 ms	205976 KiB

beauty

#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 (stderr)

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 / 100