oj.uz

답안 #21875

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
21875 2017-04-26T14:54:03 Z ulna 아름다운 순열 (IZhO12_beauty) C++11
100 / 100
 1033 ms 165860 KB 
#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

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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 165860 KB Output is correct
2 Correct 0 ms 165860 KB Output is correct
3 Correct 0 ms 165860 KB Output is correct
4 Correct 0 ms 165860 KB Output is correct
5 Correct 0 ms 165860 KB Output is correct
6 Correct 0 ms 165860 KB Output is correct
7 Correct 0 ms 165860 KB Output is correct
8 Correct 0 ms 165860 KB Output is correct
9 Correct 0 ms 165860 KB Output is correct
10 Correct 0 ms 165860 KB Output is correct
11 Correct 3 ms 165860 KB Output is correct
12 Correct 6 ms 165860 KB Output is correct
13 Correct 39 ms 165860 KB Output is correct
14 Correct 203 ms 165860 KB Output is correct
15 Correct 206 ms 165860 KB Output is correct
16 Correct 186 ms 165860 KB Output is correct
17 Correct 213 ms 165860 KB Output is correct
18 Correct 179 ms 165860 KB Output is correct
19 Correct 1033 ms 165860 KB Output is correct
20 Correct 956 ms 165860 KB Output is correct