oj.uz

Submission #669832

# Submission time Handle Problem Language Result Execution time Memory
669832 2022-12-07T12:10:08 Z sudheerays123 Beautiful row (IZhO12_beauty) C++17
0 / 100
 496 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 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(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[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 = 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 59 ms 164364 KB Output is correct
2 Correct 59 ms 164356 KB Output is correct
3 Correct 59 ms 164428 KB Output is correct
4 Correct 64 ms 164412 KB Output is correct
5 Correct 60 ms 164444 KB Output is correct
6 Correct 60 ms 164384 KB Output is correct
7 Correct 60 ms 164332 KB Output is correct
8 Correct 59 ms 164372 KB Output is correct
9 Correct 57 ms 164428 KB Output is correct
10 Correct 60 ms 164384 KB Output is correct
11 Correct 73 ms 164412 KB Output is correct
12 Correct 67 ms 164360 KB Output is correct
13 Correct 138 ms 164400 KB Output is correct
14 Correct 417 ms 164456 KB Output is correct
15 Correct 496 ms 164452 KB Output is correct
16 Correct 340 ms 164452 KB Output is correct
17 Correct 434 ms 164456 KB Output is correct
18 Correct 299 ms 164452 KB Output is correct
19 Runtime error 210 ms 262144 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -