oj.uz

Submission #163508

# Submission time Handle Problem Language Result Execution time Memory
163508 2019-11-13T15:13:51 Z tselmegkh Beautiful row (IZhO12_beauty) C++14
0 / 100
 3000 ms 164600 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(mask == ((1 << n) - 1)){
		return 1;
	}
	if(dp[mask][last] != -1)return dp[mask][last];
	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 152 ms 164588 KB Output is correct
2 Correct 142 ms 164600 KB Output is correct
3 Correct 143 ms 164472 KB Output is correct
4 Correct 142 ms 164536 KB Output is correct
5 Correct 142 ms 164412 KB Output is correct
6 Correct 144 ms 164488 KB Output is correct
7 Correct 149 ms 164456 KB Output is correct
8 Correct 164 ms 164448 KB Output is correct
9 Correct 142 ms 164444 KB Output is correct
10 Correct 146 ms 164468 KB Output is correct
11 Correct 158 ms 164472 KB Output is correct
12 Correct 156 ms 164448 KB Output is correct
13 Correct 252 ms 164472 KB Output is correct
14 Correct 590 ms 164472 KB Output is correct
15 Correct 763 ms 164572 KB Output is correct
16 Correct 545 ms 164452 KB Output is correct
17 Correct 712 ms 164476 KB Output is correct
18 Correct 442 ms 164444 KB Output is correct
19 Execution timed out 3044 ms 164472 KB Time limit exceeded
20 Halted 0 ms 0 KB -