oj.uz

답안 #82335

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
82335 2018-10-30T02:46:59 Z Just_Solve_The_Problem 아름다운 순열 (IZhO12_beauty) C++11
100 / 100
 1063 ms 164868 KB 
#include <stdio.h>
#include <algorithm>

using namespace std;

#define int long long
#define ll long long

int a[22];
int n;
int ok[22][22];

int get(int x) {
	int res = 0;
	while (x) {
		res += (x % 3 == 1);
		x /= 3;
	}
	return res;
}

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

int dp[1 << 20][20];

main() {
	int n;
	scanf("%lld", &n);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%lld", &x);
		a[i] = x;
		dp[1 << i][i]++;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ok[i][j] = (get(a[i]) == get(a[j]) || get1(a[i]) == get1(a[j]));
		}
	}
	for (int mask = 1; mask < (1 << n); mask++) {
		for (int j = 0; j < n; j++) {
			if ((mask >> j) & 1 ^ 1) continue;
			for (int k = 0; k < n; k++) {
				if (((mask >> k) & 1 ^ 1) && ok[j][k]) {
					dp[mask | (1 << k)][k] += dp[mask][j];
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans += dp[(1 << n) - 1][i];
	}
	printf("%lld", ans);
}

Compilation message

beauty.cpp:33:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
beauty.cpp: In function 'int main()':
beauty.cpp:49:20: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
    if ((mask >> j) & 1 ^ 1) continue;
        ~~~~~~~~~~~~^~~
beauty.cpp:51:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     if (((mask >> k) & 1 ^ 1) && ok[j][k]) {
          ~~~~~~~~~~~~^~~
beauty.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
beauty.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &x);
   ~~~~~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 500 KB Output is correct
3 Correct 2 ms 500 KB Output is correct
4 Correct 2 ms 532 KB Output is correct
5 Correct 2 ms 556 KB Output is correct
6 Correct 2 ms 692 KB Output is correct
7 Correct 2 ms 692 KB Output is correct
8 Correct 2 ms 692 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 2 ms 692 KB Output is correct
11 Correct 11 ms 3036 KB Output is correct
12 Correct 11 ms 3036 KB Output is correct
13 Correct 44 ms 10848 KB Output is correct
14 Correct 218 ms 41680 KB Output is correct
15 Correct 200 ms 41680 KB Output is correct
16 Correct 232 ms 41680 KB Output is correct
17 Correct 225 ms 41680 KB Output is correct
18 Correct 232 ms 41680 KB Output is correct
19 Correct 1063 ms 164868 KB Output is correct
20 Correct 923 ms 164868 KB Output is correct