Submission #370650

#	Time	Username	Problem	Language	Result	Execution time	Memory
370650		MilosMilutinovic	Beautiful row (IZhO12_beauty)	C++14	100 / 100	848 ms	164676 KiB

beauty

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN = 20;
int n, a[mxN];
ll dp[1<<mxN][mxN];
bool con[mxN][mxN];

int cnt(int x) {
	int res=0;
	while(x)
		res+=x%2, x/=2;
	return res;
}

int cnt1(int x) {
	int res=0;
	while(x)
		res+=(x%3==1?1:0), x/=3;
	return res;
}

int main() {
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> a[i];
		dp[1<<i][i]=1;
	}
	for(int i=0; i<n; ++i)
		for(int j=0; j<n; ++j)
			if(cnt(a[i])==cnt(a[j])||cnt1(a[i])==cnt1(a[j]))
				con[i][j]=true;
	for(int i=1; i<(1<<n); ++i) {
		for(int j=0; j<n; ++j) {
			if(i&(1<<j)) {
				for(int k=0; k<n; ++k) {
					if((i>>k)&1^1&&con[j][k]){
						dp[i|(1<<k)][k]+=dp[i][j];
					}
				}
			}
		}
	}
	ll ans = 0;
	for(int i=0; i<n; ++i)
		ans+=dp[(1<<n)-1][i];
	cout << ans << '\n';
	return 0;
}

Compilation message (stderr)

beauty.cpp: In function 'int main()':
beauty.cpp:39:15: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   39 |      if((i>>k)&1^1&&con[j][k]){
      |         ~~~~~~^~

• Subtask 1: 100 / 100