oj.uz

Submission #321199

# Submission time Handle Problem Language Result Execution time Memory
321199 2020-11-11T13:18:53 Z kshitij_sodani Beautiful row (IZhO12_beauty) C++14
100 / 100
 833 ms 164580 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

llo n;
llo it[30];
llo co[30];
llo co2[30];
llo dp[1<<20][20];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>it[i];
		llo x=it[i];
		while(it[i]>0){
			llo xx=it[i]%3;
			if(xx==1){
				co[i]++;
			}
			it[i]-=xx;
			it[i]/=3;
		}
		it[i]=x;
		while(it[i]>0){
			llo xx=it[i]%2;
			if(xx==1){
				co2[i]++;
			}
			it[i]-=xx;
			it[i]/=2;
		}
	}
	llo ans=0;
	for(llo i=1;i<(1<<n);i++){
		vector<llo> co3;
		for(llo j=0;j<n;j++){
			if(i&(1<<j)){
				co3.pb(j);
			}
		}
		if(co3.size()==1){
			dp[i][co3[0]]=1;
		}
		else{
			for(int jj=0;jj<co3.size();jj++){
				int j=co3[jj];
				for(auto k:co3){
					if(co[k]==co[j] or co2[j]==co2[k]){
						dp[i][j]+=dp[i-(1<<j)][k];
					}
				}
			}
		}
		if(co3.size()==n){
			for(llo j=0;j<n;j++){
				ans+=dp[i][j];
			}
		}
	}
	/*for(int i=0;i<n;i++){
		cout<<co[i]<<",,";
	}
	cout<<endl;
	for(int i=0;i<n;i++){
		cout<<co2[i]<<",,";
	}
	cout<<endl;
	cout<<dp[7][0]<<":"<<dp[7][1]<<":"<<dp[7][2]<<endl;
	cout<<dp[3][0]<<":"<<dp[3][1]<<endl;
	cout<<dp[2][1]<<endl;*/
	cout<<ans<<endl;




 
 
	return 0;
}

Compilation message

beauty.cpp: In function 'int main()':
beauty.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |    for(int jj=0;jj<co3.size();jj++){
      |                 ~~^~~~~~~~~~~
beauty.cpp:62:16: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'llo' {aka 'long long int'} [-Wsign-compare]
   62 |   if(co3.size()==n){
      |      ~~~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 9 ms 2924 KB Output is correct
12 Correct 10 ms 3052 KB Output is correct
13 Correct 49 ms 10600 KB Output is correct
14 Correct 186 ms 41316 KB Output is correct
15 Correct 225 ms 41316 KB Output is correct
16 Correct 190 ms 41316 KB Output is correct
17 Correct 207 ms 41444 KB Output is correct
18 Correct 210 ms 41428 KB Output is correct
19 Correct 833 ms 164540 KB Output is correct
20 Correct 811 ms 164580 KB Output is correct