oj.uz

Submission #163502

# Submission time Handle Problem Language Result Execution time Memory
163502 2019-11-13T15:04:01 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;

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;
}
signed main(){
	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, -1) << '\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++){
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
beauty.cpp: In function 'int main()':
beauty.cpp:47:22: warning: array subscript is below array bounds [-Warray-bounds]
  return dp[mask][last] = ans;
         ~~~~~~~~~~~~~^

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 314 ms 164472 KB Output is correct
2 Correct 177 ms 164488 KB Output is correct
3 Correct 142 ms 164472 KB Output is correct
4 Correct 142 ms 164448 KB Output is correct
5 Correct 141 ms 164416 KB Output is correct
6 Correct 146 ms 164468 KB Output is correct
7 Correct 144 ms 164444 KB Output is correct
8 Correct 144 ms 164472 KB Output is correct
9 Correct 143 ms 164472 KB Output is correct
10 Correct 143 ms 164440 KB Output is correct
11 Correct 164 ms 164408 KB Output is correct
12 Correct 157 ms 164436 KB Output is correct
13 Correct 258 ms 164472 KB Output is correct
14 Correct 705 ms 164568 KB Output is correct
15 Correct 904 ms 164560 KB Output is correct
16 Correct 582 ms 164600 KB Output is correct
17 Correct 955 ms 164600 KB Output is correct
18 Correct 501 ms 164600 KB Output is correct
19 Execution timed out 3068 ms 164472 KB Time limit exceeded
20 Halted 0 ms 0 KB -