oj.uz

Submission #82334

# Submission time Handle Problem Language Result Execution time Memory
82334 2018-10-30T02:40:15 Z Just_Solve_The_Problem Beautiful row (IZhO12_beauty) C++11
0 / 100
 11 ms 1968 KB 
#include <stdio.h>
#include <algorithm>

using namespace std;

#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("%d", &n);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &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("%d", ans);
}

Compilation message

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

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 372 KB Output is correct
3 Correct 2 ms 576 KB Output is correct
4 Correct 2 ms 576 KB Output is correct
5 Correct 2 ms 576 KB Output is correct
6 Correct 2 ms 576 KB Output is correct
7 Correct 2 ms 576 KB Output is correct
8 Correct 3 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 3 ms 644 KB Output is correct
11 Incorrect 11 ms 1968 KB Output isn't correct
12 Halted 0 ms 0 KB -