oj.uz

Submission #669834

# Submission time Handle Problem Language Result Execution time Memory
669834 2022-12-07T12:13:31 Z sudheerays123 Beautiful row (IZhO12_beauty) C++17
100 / 100
 2362 ms 164552 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 twocount(ll x){

	ll cnt = 0;

	while(x){
		if(x%2 == 1) cnt++;
		x /= 2;
	}

	return cnt;
}

ll threecount(ll x){

	ll cnt = 0;

	while(x){
		if(x%3 == 1) cnt++;
		x /= 3;
	}

	return cnt;
}

ll c2[N],c3[N];
ll n;
ll dp[(1ll<<N)][N];

ll go(ll mask , ll last){

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

	ll ans = 0;

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

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

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

void solve(){

	cin >> n;
	vector<ll> a(n+5);

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

	memset(dp,-1,sizeof dp);

	cout << go(0,-1);
}

int main(){

	fast;

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

	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 164428 KB Output is correct
2 Correct 58 ms 164428 KB Output is correct
3 Correct 58 ms 164440 KB Output is correct
4 Correct 60 ms 164360 KB Output is correct
5 Correct 59 ms 164336 KB Output is correct
6 Correct 60 ms 164376 KB Output is correct
7 Correct 64 ms 164340 KB Output is correct
8 Correct 59 ms 164360 KB Output is correct
9 Correct 60 ms 164432 KB Output is correct
10 Correct 69 ms 164416 KB Output is correct
11 Correct 69 ms 164416 KB Output is correct
12 Correct 69 ms 164464 KB Output is correct
13 Correct 110 ms 164428 KB Output is correct
14 Correct 359 ms 164384 KB Output is correct
15 Correct 434 ms 164552 KB Output is correct
16 Correct 297 ms 164428 KB Output is correct
17 Correct 384 ms 164368 KB Output is correct
18 Correct 252 ms 164356 KB Output is correct
19 Correct 2154 ms 164372 KB Output is correct
20 Correct 2362 ms 164456 KB Output is correct