oj.uz

Submission #163507

# Submission time Handle Problem Language Result Execution time Memory
163507 2019-11-13T15:13:02 Z tselmegkh Beautiful row (IZhO12_beauty) C++14
0 / 100
 3000 ms 164700 KB 
#include<bits/stdc++.h>
using namespace std;

vector<int> binary[33], trinary[33];
vector<int> a;
int n;

inline int count(int x){
	int res = 0;
	while(x > 0){
		if(x % 3 == 1){
			res++;
		}
		x /= 3;
	}
	return res;
}

int cnttri[20];
long long dp[(1 << 20)][20];
inline long long solve(int mask, int last){
	if(dp[mask][last] != -1)return dp[mask][last];
	if(mask == ((1 << n) - 1)){
		return 1;
	}
	long long ans = 0;
	if(mask == 0){
		for(int j = 0; j < n; j++){
			int curmask = mask | (1 << j);
			ans += solve(curmask, j);
		}
	}
	else{
		int binaryones = __builtin_popcount(a[last]), trinaryones = cnttri[last];
		for(int j = 0; j < binary[binaryones].size(); j++){
			int k = binary[binaryones][j];
			if(mask & (1 << k))continue;
			int curmask = mask | (1 << k);
			ans += solve(curmask, k);
		}
		for(int j = 0; j < trinary[trinaryones].size(); j++){
			int k = trinary[trinaryones][j];
			if(mask & (1 << k))continue;
			int curmask = mask | (1 << k);
			if(!(binaryones == __builtin_popcount(a[k])))ans += solve(curmask, k);
		}
	}
	return dp[mask][last] = ans;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	a.resize(n);

	for(int i = 0; i < n; i++){
		cin >> a[i];
		int cnt3 = count(a[i]), cnt2 = __builtin_popcount(a[i]);
		binary[cnt2].push_back(i);
		trinary[cnt3].push_back(i);
		cnttri[i] = cnt3;
	}
	memset(dp, -1, sizeof dp);

	cout << solve(0, 0) << '\n';
}

Compilation message

beauty.cpp: In function 'long long int solve(int, int)':
beauty.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < binary[binaryones].size(); j++){
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
beauty.cpp:41:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < trinary[trinaryones].size(); j++){
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 164472 KB Output is correct
2 Correct 141 ms 164472 KB Output is correct
3 Correct 167 ms 164500 KB Output is correct
4 Correct 141 ms 164472 KB Output is correct
5 Correct 149 ms 164508 KB Output is correct
6 Correct 147 ms 164540 KB Output is correct
7 Correct 142 ms 164480 KB Output is correct
8 Correct 142 ms 164512 KB Output is correct
9 Correct 145 ms 164452 KB Output is correct
10 Correct 145 ms 164472 KB Output is correct
11 Correct 159 ms 164600 KB Output is correct
12 Correct 157 ms 164620 KB Output is correct
13 Correct 263 ms 164452 KB Output is correct
14 Correct 575 ms 164700 KB Output is correct
15 Correct 709 ms 164604 KB Output is correct
16 Correct 473 ms 164524 KB Output is correct
17 Correct 674 ms 164476 KB Output is correct
18 Correct 452 ms 164600 KB Output is correct
19 Correct 2896 ms 164572 KB Output is correct
20 Execution timed out 3054 ms 164472 KB Time limit exceeded