oj.uz

Submission #163505

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

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

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

long long dp[(1 << 20)][20];
long long solve(int mask, int 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{
		if(dp[mask][last] != -1)return dp[mask][last];
		int binaryones = __builtin_popcount(a[last]), trinaryones = count(a[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);
	}
	memset(dp, -1, sizeof dp);

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

Compilation message

beauty.cpp: In function 'long long int solve(int, int)':
beauty.cpp:34:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < binary[binaryones].size(); j++){
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
beauty.cpp:40: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 148 ms 164608 KB Output is correct
2 Correct 142 ms 164472 KB Output is correct
3 Correct 142 ms 164600 KB Output is correct
4 Correct 148 ms 164472 KB Output is correct
5 Correct 143 ms 164600 KB Output is correct
6 Correct 152 ms 164492 KB Output is correct
7 Correct 142 ms 164472 KB Output is correct
8 Correct 153 ms 164472 KB Output is correct
9 Correct 149 ms 164472 KB Output is correct
10 Correct 175 ms 164636 KB Output is correct
11 Correct 172 ms 164476 KB Output is correct
12 Correct 160 ms 164492 KB Output is correct
13 Correct 268 ms 164472 KB Output is correct
14 Correct 727 ms 164528 KB Output is correct
15 Correct 865 ms 164600 KB Output is correct
16 Correct 582 ms 164472 KB Output is correct
17 Correct 831 ms 164600 KB Output is correct
18 Correct 526 ms 164604 KB Output is correct
19 Execution timed out 3061 ms 164600 KB Time limit exceeded
20 Halted 0 ms 0 KB -