oj.uz

Submission #338670

# Submission time Handle Problem Language Result Execution time Memory
338670 2020-12-23T15:56:19 Z amunduzbaev Beautiful row (IZhO12_beauty) C++14
100 / 100
 844 ms 189248 KB 
/** made by amunduzbaev **/
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long 
#define ld long double 
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}

const int N = 23;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);

int n, m, k, ans, a[N];
bool path[N][N];
ll dp[1<<N][N];

int cnt(int x){ 
	int cnt = 0; 
	while(x) cnt += (x%2 == 1), x/=2; 
	return cnt;
}
int cnt1(int x){
	int cnt = 0; 
	while(x) cnt += (x%3 == 1), x/=3; 
	return cnt;
}

void solve(){
	fastios 
	cin>>n;
	for(int i=0; i<n; i++) cin>>a[i];
	for(int i=0; i<n; i++)
		for(int j=0;j<n;j++) { if(i == j) continue; 
			if(cnt(a[i]) == cnt(a[j]) || cnt1(a[i]) == cnt1(a[j])) path[i][j] = 1; }
	
	for(int i=0; i<(n); i++) dp[1<<i][i] = 1;
	for(int i=1; i<(1<<n); i++){
		for(int j=0; j<n; j++){
			if(i & (1<<j)){
				for(int t=0; t<n; t++)
					if(j != t && path[j][t] && (i&(1<<t))) dp[i][j] += dp[i ^ (1<<j)][t];
			}
		}
	}
	ll ans = 0;	
	for(int i=0;i<n;i++) ans += dp[(1<<n)-1][i];
	cout<<ans<<"\n";
	return;
}
 
 
int main(){
	fastios
	int t = 1;
	if(t) solve();
	else {
		cin>>t;
		while (t--) solve();
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 9 ms 3308 KB Output is correct
12 Correct 9 ms 3308 KB Output is correct
13 Correct 46 ms 12268 KB Output is correct
14 Correct 192 ms 47472 KB Output is correct
15 Correct 188 ms 47724 KB Output is correct
16 Correct 175 ms 47596 KB Output is correct
17 Correct 185 ms 47596 KB Output is correct
18 Correct 156 ms 47596 KB Output is correct
19 Correct 842 ms 189164 KB Output is correct
20 Correct 844 ms 189248 KB Output is correct