Submission #636846

#	Time	Username	Problem	Language	Result	Execution time	Memory
636846		zeroesandones	Beautiful row (IZhO12_beauty)	C++17	100 / 100	399 ms	164456 KiB

beauty

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;

#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define sp " "

#define all(x) (x).begin(), (x).end()
#define sc second
#define fr first
#define pb push_back

ll get(int x, int y) {
	ll res = 0;
	while(x) {
		res += (x % y == 1);
		x /= y;
	}
	return res;
}

void solve()
{
    int n;
    cin >> n;

    vi a(n);
    for(auto &i : a) {
		cin >> i;
	}
        
	bool spec[n][n] = {};

	FOR(i, 0, n) {
		FOR(j, 0, n) {
			spec[i][j] = (get(a[i], 2) == get(a[j], 2) || get(a[i], 3) == get(a[j], 3));
		}
	}

	ll dp[(1<<n)][n] = {};

	FOR(s, 0, (1<<n)) {
		FOR(i, 0, n) {
			ll curr = (1<<i);
			if((curr & s) == 0)
				continue;
			
			ll last = s ^ curr;
			if(last == 0) {
				dp[s][i] = 1;
				continue;
			}

			FOR(j, 0, n) {
				if(i == j) 
					continue;
				if(!spec[i][j])
					continue;
				dp[s][i] += dp[last][j];
				
			}
		}
	}

	ll ans = 0;
	FOR(i, 0, n) {
		ans += dp[(1 << n) - 1][i];
	}
	cout << ans << nl;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
}

• Subtask 1: 100 / 100