oj.uz

Submission #669779

# Submission time Handle Problem Language Result Execution time Memory
669779 2022-12-07T09:13:31 Z sudheerays123 Beautiful row (IZhO12_beauty) C++17
0 / 100
 3000 ms 164460 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 = 1e18 , MOD = 1e9+7;

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

ll twocount(ll x){

	ll s = 1;
	while(s <= x) s *= 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) s *= 3;
	s /= 3;

	ll cnt = 0;

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

	return cnt;
}

ll go(ll mask , ll last){

	if(twocount(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(twocount(a[last]) == twocount(a[i]) || threecount(a[last]) == threecount(a[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];

	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 63 ms 164404 KB Output is correct
2 Correct 62 ms 164424 KB Output is correct
3 Correct 67 ms 164356 KB Output is correct
4 Correct 62 ms 164400 KB Output is correct
5 Correct 63 ms 164380 KB Output is correct
6 Correct 72 ms 164432 KB Output is correct
7 Correct 62 ms 164432 KB Output is correct
8 Correct 66 ms 164432 KB Output is correct
9 Correct 63 ms 164428 KB Output is correct
10 Correct 73 ms 164416 KB Output is correct
11 Correct 291 ms 164456 KB Output is correct
12 Correct 242 ms 164428 KB Output is correct
13 Correct 1200 ms 164460 KB Output is correct
14 Execution timed out 3076 ms 164364 KB Time limit exceeded
15 Halted 0 ms 0 KB -