Submission #682100

#	Time	Username	Problem	Language	Result	Execution time	Memory
682100		Hydrolyzed	Beautiful row (IZhO12_beauty)	C++14	100 / 100	2768 ms	164548 KiB

beauty

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MxN = 20;
ll dp[1 << MxN][MxN], a[MxN];

int count_three(ll x){
	int response = 0;
	while(x > 0){
		response += (x % 3 == 1);
		x /= 3;
	}
	return response;
}

bool ok(ll a, ll b){
	return (__builtin_popcountll(a) == __builtin_popcountll(b) || count_three(a) == count_three(b));
}

void solve(){
	memset(dp, 0, sizeof dp);
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; ++i){
		scanf("%lld", &a[i]);
		dp[1 << i][i] = 1;
	}
	for(int state=1; state<(1 << n); ++state){
		for(int i=0; i<n; ++i){
			if(!(state & (1 << i))){
				continue;
			}
			for(int j=0; j<n; ++j){
				if(state & (1 << j)){
					continue;
				}
				if(ok(a[i], a[j])){
					dp[state ^ (1 << j)][j] += dp[state][i];
				}
			}
		}
	}
	ll answer = 0ll;
	for(int i=0; i<n; ++i){
		answer = answer + dp[(1 << n) - 1][i];
	}
	printf("%lld", answer);
}

int main(){
	int q = 1;
	//scanf("%d", &q);
	while(q--){
		solve();
		printf("\n");
	}
	return 0;
}

Compilation message (stderr)

beauty.cpp: In function 'void solve()':
beauty.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
beauty.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf("%lld", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 100 / 100