oj.uz

Submission #669790

# Submission time Handle Problem Language Result Execution time Memory
669790 2022-12-07T09:26:21 Z sudheerays123 Beautiful row (IZhO12_beauty) C++17
0 / 100
 477 ms 262144 KB 
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
const ll N = 20 , INF = 1e9 , MOD = 1e9+7;

ll n;
ll dp[(1ll<<N)+5][N+5];
vector<ll> a(N+5);

ll twocount(ll x){

	ll s = 1;
	while(s <= (x/2)) s *= 2;

	ll cnt = 0;

	while(x){
		ll p = x/s;
		x -= p*s;
		if(p == 1) cnt++;
		s /= 2;
	}

	return cnt;
}

ll threecount(ll x){

	ll s = 1;
	while(s <= (x/3)) s *= 3;

	ll cnt = 0;

	while(x){
		ll p = x/s;
		x -= p*s;
		if(p == 1) cnt++;
		s /= 3;
	}

	return cnt;
}

ll c2[N+5] , c3[N+5];

ll go(ll mask , ll last){

	if(__builtin_popcountll(mask) == n) return 1;
	if(dp[mask][last] != -1) return dp[mask][last];

	ll ans = 0;

	for(ll i = 1; i <= n; i++){
		if(mask&(1ll<<i)) continue;

		if(last == 0) ans += go(mask|(1ll<<i),i);
		else if(c2[last] == c2[i] || c3[last] == c3[i]) ans += go(mask|(1ll<<i),i);
	}

	return dp[mask][last] = ans;
}

void solve(){

	cin >> n;
	for(ll i = 1; i <= n; i++){
		cin >> a[i];
		c2[i] = twocount(a[i]);
		c3[i] = threecount(a[i]);
	}

	memset(dp,-1,sizeof dp);

	cout << go(0,0);
}

int main(){

	fast;


	ll tc = 1;
	// cin >> tc;
	while(tc--) solve();

	return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 205472 KB Output is correct
2 Correct 79 ms 205492 KB Output is correct
3 Correct 97 ms 205388 KB Output is correct
4 Correct 75 ms 205492 KB Output is correct
5 Correct 76 ms 205492 KB Output is correct
6 Correct 76 ms 205488 KB Output is correct
7 Correct 77 ms 205516 KB Output is correct
8 Correct 79 ms 205372 KB Output is correct
9 Correct 79 ms 205416 KB Output is correct
10 Correct 85 ms 205400 KB Output is correct
11 Correct 87 ms 205496 KB Output is correct
12 Correct 83 ms 205460 KB Output is correct
13 Correct 137 ms 205484 KB Output is correct
14 Correct 404 ms 205480 KB Output is correct
15 Correct 477 ms 205508 KB Output is correct
16 Correct 335 ms 205388 KB Output is correct
17 Correct 435 ms 205532 KB Output is correct
18 Correct 288 ms 205504 KB Output is correct
19 Runtime error 266 ms 262144 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -