oj.uz

Submission #41212

# Submission time Handle Problem Language Result Execution time Memory
41212 2018-02-14T03:16:08 Z MatheusLealV Beautiful row (IZhO12_beauty) C++14
0 / 100
 3000 ms 173424 KB 
#include <bits/stdc++.h>
#define N 21
#define M 1050000
using namespace std;
typedef long long ll;

ll n, dp[N][M], v[N], pot[45], qtd[N][5];

vector<int> grafo[N];

bool equal(int a, int b)
{
	return (qtd[a][2] == qtd[b][2] || qtd[a][3] == qtd[b][3]);
}

int ternary(int x)
{
	int cnt = 0;

	for(int log3 = 30; log3 >= 0; log3 --)
	{
		ll aux = pot[log3], qaux = 0;

		if(x >= aux)
		{
			x -= aux;

			qaux ++;
		}

		if(x >= aux)
		{
			x -= aux;

			qaux ++;
		}

		cnt = cnt + (qaux == 1);
	}

	return cnt;
}

ll solve(int x, int mask)
{
	if(dp[x][mask] != -1) return dp[x][mask];

	if(mask == (1<<n) - 1) return 1;

	dp[x][mask] = 0;

	for(int v = 0; v < n; v++)
	{
		if(mask & (1<<v)) continue;

		if(equal(x, v)) dp[x][mask] += solve(v, mask | (1<<v));
	}

	return dp[x][mask];
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n;

	for(int i = 0; i < n; i++) cin>>v[i];

	pot[0] = 1;

	for(int i = 1; i < 45; i++) pot[i] = pot[i - 1]*3;

	for(int i = 0; i < n; i++)
	{
		qtd[i][2] = __builtin_popcount (v[i]);

		qtd[i][3] = ternary(v[i]);
	}

	memset(dp, -1, sizeof dp);

	ll best = 0;

	for(int i = 0; i < n; i++) best += solve(i, 1<<i);

	cout<<best<<"\n";
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 172920 KB Output is correct
2 Correct 126 ms 172964 KB Output is correct
3 Correct 121 ms 173096 KB Output is correct
4 Correct 121 ms 173136 KB Output is correct
5 Correct 126 ms 173140 KB Output is correct
6 Correct 128 ms 173192 KB Output is correct
7 Correct 125 ms 173256 KB Output is correct
8 Correct 123 ms 173256 KB Output is correct
9 Correct 122 ms 173256 KB Output is correct
10 Correct 119 ms 173256 KB Output is correct
11 Correct 136 ms 173256 KB Output is correct
12 Correct 127 ms 173256 KB Output is correct
13 Correct 182 ms 173256 KB Output is correct
14 Correct 580 ms 173272 KB Output is correct
15 Correct 601 ms 173308 KB Output is correct
16 Correct 448 ms 173308 KB Output is correct
17 Correct 547 ms 173424 KB Output is correct
18 Correct 380 ms 173424 KB Output is correct
19 Correct 2931 ms 173424 KB Output is correct
20 Execution timed out 3029 ms 173424 KB Time limit exceeded