oj.uz

Submission #163509

# Submission time Handle Problem Language Result Execution time Memory
163509 2019-11-13T15:14:28 Z tselmegkh Beautiful row (IZhO12_beauty) C++14
100 / 100
 2839 ms 164652 KB 
#include<bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

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:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
beauty.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
beauty.cpp: In function 'long long int solve(int, int)':
beauty.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < binary[binaryones].size(); j++){
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
beauty.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0; j < trinary[trinaryones].size(); j++){
                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 164600 KB Output is correct
2 Correct 154 ms 164472 KB Output is correct
3 Correct 142 ms 164476 KB Output is correct
4 Correct 150 ms 164472 KB Output is correct
5 Correct 143 ms 164472 KB Output is correct
6 Correct 145 ms 164552 KB Output is correct
7 Correct 143 ms 164592 KB Output is correct
8 Correct 142 ms 164492 KB Output is correct
9 Correct 143 ms 164500 KB Output is correct
10 Correct 155 ms 164472 KB Output is correct
11 Correct 172 ms 164600 KB Output is correct
12 Correct 154 ms 164632 KB Output is correct
13 Correct 216 ms 164472 KB Output is correct
14 Correct 522 ms 164600 KB Output is correct
15 Correct 632 ms 164472 KB Output is correct
16 Correct 437 ms 164472 KB Output is correct
17 Correct 656 ms 164472 KB Output is correct
18 Correct 386 ms 164652 KB Output is correct
19 Correct 2523 ms 164472 KB Output is correct
20 Correct 2839 ms 164620 KB Output is correct