Submission #336131

#	Time	Username	Problem	Language	Result	Execution time	Memory
336131		tevdore	Beautiful row (IZhO12_beauty)	C++14	100 / 100	911 ms	205804 KiB

beauty

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
int const N = 1 << 23;
int n;
ll a[25], dp[N][25], F1[25], F2[25];
ll ans;
int bin(ll x) {
	int r = 0;
	while(x) {
		r += x % 2;
		x /= 2;
	}
	return r;
}
int ter(ll x) {
	int r = 0;
	while(x) {
		r += (x % 3 == 1);
		x /= 3;
	}
	return r;
}
main() {
	ios::sync_with_stdio(0);
	cin.tie();
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	int mask = 1 << n;
	mask--;
	for(int i = 1; i <= n; i++) {
		F1[i] = bin(a[i]);
		F2[i] = ter(a[i]);
	}
	for(int i = 1; i <= mask; i++) {
		for(int j = 0; j < n; j++) {
			if(i >> j & 1) {
				int x = i ^ (1 << j);
				if(!x) {
					dp[i][j + 1] = 1;
					continue;
				}
				for(int z = 0; z < n; z++) {
					if((x >> z) & 1) {
						bool f1 = false, f2 = false;
						f1 = (F1[j + 1] == F1[z + 1]);
						f2 = (F2[j + 1] == F2[z + 1]);
						if(f1 || f2) dp[i][j + 1] += dp[x][z + 1];
					}
				}
			}
		}
	}
	for(int j = 0; j < n; j++) ans += dp[mask][j + 1];
	cout << ans << "\n";
}

Compilation message (stderr)

beauty.cpp:24:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main() {
      |      ^

• Subtask 1: 100 / 100