oj.uz

Submission #648120

# Submission time Handle Problem Language Result Execution time Memory
648120 2022-10-05T12:30:30 Z starchan Beautiful row (IZhO12_beauty) C++17
100 / 100
 854 ms 127592 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
int cnt2(int n)
{
	int ans = 0;
	while(n)
	{
		ans+=(n%2==1);
		n/=2;
	}
	return ans;
}
int cnt3(int n)
{
	int ans = 0;
	while(n)
	{
		ans+=(n%3==1);
		n/=3;
	}
	return ans;
}
int dp[20][1ll<<20];
signed main()
{
	fast();
	int n;
	cin >> n;
	vector<vector<int>> adj(n);
	vector<in> a(n);
	for(int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		a[i] = {cnt2(x), cnt3(x)};
		for(int j = 0; j < i; j++)
		{
			if(a[i].f == a[j].f || a[i].s == a[j].s)
			{
				adj[i].pb(j);
				adj[j].pb(i);
			}
		}
	}
	int ans = 0;
	for(int j = 1; j < (1ll<<n); j++)
	{
		for(int i = 0; i < n; i++)
		{
			if((j^(1ll<<i)) > j)
				continue;
			int k = j^(1ll<<i);
			if(k==0)
			{
				dp[i][j] = 1;
				continue;
			}
			dp[i][j] = 0;
			for(int v: adj[i])
			{
				if((k^(1ll<<v)) > k)
					continue;
				dp[i][j]+=dp[v][k];
			}
		}
	}
	for(int i = 0; i < n; i++)
		ans+=dp[i][(1ll<<n)-1];
	cout << ans;
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 9 ms 1920 KB Output is correct
12 Correct 7 ms 1984 KB Output is correct
13 Correct 35 ms 7364 KB Output is correct
14 Correct 162 ms 30164 KB Output is correct
15 Correct 185 ms 30260 KB Output is correct
16 Correct 138 ms 30060 KB Output is correct
17 Correct 157 ms 30160 KB Output is correct
18 Correct 116 ms 30136 KB Output is correct
19 Correct 774 ms 127548 KB Output is correct
20 Correct 854 ms 127592 KB Output is correct