Submission #21875

#	Time	Username	Problem	Language	Result	Execution time	Memory
21875		ulna	Beautiful row (IZhO12_beauty)	C++11	100 / 100	1033 ms	165860 KiB

beauty

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

// why am I so weak

int n;
int a[25];
long long dp[1 << 20][20];

bool adj[25][25];

inline bool gao(int x, int y, int t) {
	int a = 0;

	while (x > 0) {
		if (x % t == 1) a++;
		x /= t;
	}

	while (y > 0) {
		if (y % t == 1) a--;
		y /= t;
	}

	return a == 0;
}
bool trial(int x, int y) {
	return gao(x, y, 2) || gao(x, y, 3);
}
int main() {
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		dp[1 << i][i] = 1;
	}

	for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
		adj[i][j] = trial(a[i], a[j]);
	}

	for (int mask = 0; mask < (1 << n); mask++) {
		for (int i = 0; i < n; i++) if (dp[mask][i] > 0) {
			for (int j = 0; j < n; j++) if (!(mask & (1 << j)) && adj[i][j]) {
				dp[mask | (1 << j)][j] += dp[mask][i];
			}
		}
	}

	long long res = 0ll;

	for (int i = 0; i < n; i++) res += dp[(1 << n) - 1][i];

	printf("%lld\n", res);

	return 0;
}

Compilation message (stderr)

beauty.cpp: In function 'int main()':
beauty.cpp:31:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
beauty.cpp:34:21: 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