oj.uz

Submission #683848

# Submission time Handle Problem Language Result Execution time Memory
683848 2023-01-19T13:30:57 Z vovamr Beautiful row (IZhO12_beauty) C++17
100 / 100
 935 ms 205520 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

inline void solve() {
	int n;
	cin >> n;
	ve<pii> a(n);
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;

		a[i].fi = __builtin_popcount(x);

		int cnt = 0;
		while (x > 0) {
			cnt += (x % 3 == 1);
			x /= 3;
		}
		a[i].se = cnt;
	}

	ve<ve<ll>> dp(1 << n, ve<ll> (n));
	for (int i = 0; i < n; ++i) dp[1 << i][i] = 1;

	for (int ma = 0; ma < (1 << n); ++ma) {
		for (int i = 0; i < n; ++i) {
			if (ma >> i & 1 ^ 1) continue;
			for (int j = 0; j < n; ++j) {
				if (ma >> j & 1) continue;
				if (a[i].fi == a[j].fi || a[i].se == a[j].se) {
					dp[ma | (1 << j)][j] += dp[ma][i];
				}
			}
		}
	}

	ll ans = 0;
	for (int i = 0; i < n; ++i) ans += dp[(1 << n) - 1][i];

	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message

beauty.cpp: In function 'void solve()':
beauty.cpp:46:16: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   46 |    if (ma >> i & 1 ^ 1) continue;
      |        ~~~~~~~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 324 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 320 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 324 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 10 ms 2816 KB Output is correct
12 Correct 7 ms 2644 KB Output is correct
13 Correct 36 ms 11096 KB Output is correct
14 Correct 174 ms 47424 KB Output is correct
15 Correct 166 ms 47520 KB Output is correct
16 Correct 204 ms 47516 KB Output is correct
17 Correct 200 ms 47512 KB Output is correct
18 Correct 199 ms 47500 KB Output is correct
19 Correct 935 ms 205520 KB Output is correct
20 Correct 773 ms 205520 KB Output is correct