oj.uz

Submission #163506

# Submission time Handle Problem Language Result Execution time Memory
163506 2019-11-13T15:11:15 Z tselmegkh Beautiful row (IZhO12_beauty) C++14
0 / 100
 3000 ms 164632 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(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 = 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 140 ms 164516 KB Output is correct
2 Correct 152 ms 164472 KB Output is correct
3 Correct 145 ms 164476 KB Output is correct
4 Correct 142 ms 164472 KB Output is correct
5 Correct 144 ms 164428 KB Output is correct
6 Correct 154 ms 164524 KB Output is correct
7 Correct 151 ms 164516 KB Output is correct
8 Correct 150 ms 164428 KB Output is correct
9 Correct 146 ms 164512 KB Output is correct
10 Correct 145 ms 164556 KB Output is correct
11 Correct 166 ms 164600 KB Output is correct
12 Correct 159 ms 164596 KB Output is correct
13 Correct 258 ms 164612 KB Output is correct
14 Correct 732 ms 164472 KB Output is correct
15 Correct 880 ms 164632 KB Output is correct
16 Correct 626 ms 164604 KB Output is correct
17 Correct 808 ms 164472 KB Output is correct
18 Correct 514 ms 164620 KB Output is correct
19 Execution timed out 3029 ms 164472 KB Time limit exceeded
20 Halted 0 ms 0 KB -