oj.uz

Submission #682100

# Submission time Handle Problem Language Result Execution time Memory
682100 2023-01-15T17:44:57 Z Hydrolyzed Beautiful row (IZhO12_beauty) C++14
100 / 100
 2768 ms 164548 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MxN = 20;
ll dp[1 << MxN][MxN], a[MxN];

int count_three(ll x){
	int response = 0;
	while(x > 0){
		response += (x % 3 == 1);
		x /= 3;
	}
	return response;
}

bool ok(ll a, ll b){
	return (__builtin_popcountll(a) == __builtin_popcountll(b) || count_three(a) == count_three(b));
}

void solve(){
	memset(dp, 0, sizeof dp);
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; ++i){
		scanf("%lld", &a[i]);
		dp[1 << i][i] = 1;
	}
	for(int state=1; state<(1 << n); ++state){
		for(int i=0; i<n; ++i){
			if(!(state & (1 << i))){
				continue;
			}
			for(int j=0; j<n; ++j){
				if(state & (1 << j)){
					continue;
				}
				if(ok(a[i], a[j])){
					dp[state ^ (1 << j)][j] += dp[state][i];
				}
			}
		}
	}
	ll answer = 0ll;
	for(int i=0; i<n; ++i){
		answer = answer + dp[(1 << n) - 1][i];
	}
	printf("%lld", answer);
}

int main(){
	int q = 1;
	//scanf("%d", &q);
	while(q--){
		solve();
		printf("\n");
	}
	return 0;
}

Compilation message

beauty.cpp: In function 'void solve()':
beauty.cpp:25:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
beauty.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf("%lld", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 164428 KB Output is correct
2 Correct 71 ms 164360 KB Output is correct
3 Correct 61 ms 164396 KB Output is correct
4 Correct 59 ms 164440 KB Output is correct
5 Correct 60 ms 164356 KB Output is correct
6 Correct 61 ms 164368 KB Output is correct
7 Correct 62 ms 164428 KB Output is correct
8 Correct 64 ms 164428 KB Output is correct
9 Correct 60 ms 164408 KB Output is correct
10 Correct 67 ms 164324 KB Output is correct
11 Correct 78 ms 164432 KB Output is correct
12 Correct 74 ms 164364 KB Output is correct
13 Correct 138 ms 164356 KB Output is correct
14 Correct 573 ms 164444 KB Output is correct
15 Correct 301 ms 164440 KB Output is correct
16 Correct 681 ms 164444 KB Output is correct
17 Correct 629 ms 164548 KB Output is correct
18 Correct 812 ms 164444 KB Output is correct
19 Correct 2768 ms 164536 KB Output is correct
20 Correct 1165 ms 164440 KB Output is correct