Submission #730852

#	Time	Username	Problem	Language	Result	Execution time	Memory
730852		rainboy	Beautiful row (IZhO12_beauty)	C11	100 / 100	736 ms	164420 KiB

beauty

#include <stdio.h>

#define N	20

int ones(int n, int b) {
	return n == 0 ? 0 : ones(n / b, b) + (n % b == 1 ? 1 : 0);
}

int main() {
	static int aa[N];
	static char adj[N][N];
	static long long dp[1 << N][N];
	int n, i, j, b;
	long long ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &aa[i]);
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			adj[i][j] = ones(aa[i], 2) == ones(aa[j], 2) || ones(aa[i], 3) == ones(aa[j], 3);
	for (i = 0; i < n; i++)
		dp[1 << i][i] = 1;
	for (b = 0; b < 1 << n; b++)
		for (i = 0; i < n; i++) {
			long long x = dp[b][i];

			if (x == 0)
				continue;
			for (j = 0; j < n; j++)
				if ((b & 1 << j) == 0 && adj[i][j])
					dp[b | 1 << j][j] += dp[b][i];
		}
	b = (1 << n) - 1;
	ans = 0;
	for (i = 0; i < n; i++)
		ans += dp[b][i];
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

beauty.c: In function 'main':
beauty.c:16:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |  scanf("%d", &n);
      |  ^~~~~~~~~~~~~~~
beauty.c:18:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |   scanf("%d", &aa[i]);
      |   ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100