oj.uz

Submission #682099

# Submission time Handle Problem Language Result Execution time Memory
682099 2023-01-15T17:44:31 Z Hydrolyzed Beautiful row (IZhO12_beauty) C++14
0 / 100
 79 ms 164472 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;
	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]);
      |   ~~~~~^~~~~~~~~~~~~~~
beauty.cpp: In function 'int main()':
beauty.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 164472 KB Output isn't correct
2 Halted 0 ms 0 KB -