oj.uz

Submission #83185

# Submission time Handle Problem Language Result Execution time Memory
83185 2018-11-05T22:52:07 Z nikolapesic2802 Beautiful row (IZhO12_beauty) C++14
100 / 100
 1058 ms 164828 KB 
#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
#define int long long
#define ll long long
 
int a[22];
int n;
// can these two elements i and j be neighbours?
int ok[22][22];
 
// return number of '1' in ternary representation
int get(int x) {
	int res = 0;
	while (x) {
		res += (x % 3 == 1);
		x /= 3;
	}
	return res;
}
 
// return number of '1' in binary representation
int get1(int x) {
	int res = 0;
	while (x) {
		res += (x % 2 == 1);
		x /= 2;
	}
	return res;
}
 
 /*
dp[mask][i] = mask shows which elements we took, it avoids to take element twice
              i shows which element we took last, it avoids to calc wrong permutation
*/
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;
    // initially we can take an element i 
		dp[1 << i][i]++;
	}
  // precalc ok[i][j]
	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;
      // we push value of dp[mask][j] to front
      // if element j is not taken, skip it
      // because we add to the dp[mask | (1 << k)][k] the value dp[mask][j]
      // we can't add dp[mask][j] if we didn't took it
			for (int k = 0; k < n; k++) {
				if (((mask >> k) & 1 ^ 1) && ok[j][k]) {
          // if we can take an element k after element j
          // we push value front
					dp[mask | (1 << k)][k] += dp[mask][j];
				}
			}
		}
	}
  // answer is sum of ( dp[2^n - 1][i] ): 0 <= i <= n - 1 
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans += dp[(1 << n) - 1][i];
	}
	printf("%lld", ans);
}

Compilation message

beauty.cpp:40:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
beauty.cpp: In function 'int main()':
beauty.cpp:58:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
       if ((mask >> j) & 1 ^ 1) continue;
           ~~~~~~~~~~~~^~~
beauty.cpp:64:22: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
     if (((mask >> k) & 1 ^ 1) && ok[j][k]) {
          ~~~~~~~~~~~~^~~
beauty.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
beauty.cpp:45: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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 2 ms 756 KB Output is correct
7 Correct 2 ms 756 KB Output is correct
8 Correct 2 ms 756 KB Output is correct
9 Correct 2 ms 772 KB Output is correct
10 Correct 2 ms 772 KB Output is correct
11 Correct 12 ms 2992 KB Output is correct
12 Correct 11 ms 2992 KB Output is correct
13 Correct 46 ms 10804 KB Output is correct
14 Correct 222 ms 41520 KB Output is correct
15 Correct 201 ms 41704 KB Output is correct
16 Correct 220 ms 41704 KB Output is correct
17 Correct 221 ms 41704 KB Output is correct
18 Correct 227 ms 41704 KB Output is correct
19 Correct 1058 ms 164824 KB Output is correct
20 Correct 922 ms 164828 KB Output is correct