oj.uz

Submission #848295

# Submission time Handle Problem Language Result Execution time Memory
848295 2023-09-12T02:53:30 Z wakandaaa Beautiful row (IZhO12_beauty) C++17
100 / 100
 1837 ms 158420 KB 
#include <bits/stdc++.h>

using namespace std;

#define file ""

#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()

#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1LL << (x))
#define popcount __builtin_popcountll

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
    return l + rd() % (r - l + 1);
}

const int N = 20;
const int mod = (int)1e9 + 7; // 998244353;
const int lg = 25; // lg + 1
const int oo = 1e9;
const long long ooo = 1e18;

template<class X, class Y> bool mini(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maxi(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

int n;
int a[N], b[N];
long long f[N][1 << N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);

    cin >> n;
    for (int i = 0; i < n; ++i) {
    	int x;
    	cin >> x;
    	a[i] = popcount(x);
    	while (x) {
    		if (x % 3 == 1) ++b[i];
    		x /= 3;
    	}
    }

    for (int i = 0; i < n; ++i) f[i][bit(i)] = 1;
    for (int mask = 0; mask < bit(n); ++mask) {
    	for (int i = 0; i < n; ++i) if (getbit(mask, i)) {
    		for (int j = 0; j < n; ++j) if (getbit(mask, j)) {
    			if (a[i] == a[j] || b[i] == b[j])
    				f[i][mask] += f[j][mask ^ bit(i)];
    		}
    	}
    }

    long long res = 0;
    for (int i = 0; i < n; ++i) res += f[i][bit(n) - 1];

    cout << res;

    return 0;
}

/*

*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 6488 KB Output is correct
4 Correct 1 ms 6488 KB Output is correct
5 Correct 3 ms 6488 KB Output is correct
6 Correct 3 ms 18776 KB Output is correct
7 Correct 3 ms 18976 KB Output is correct
8 Correct 2 ms 18776 KB Output is correct
9 Correct 3 ms 18776 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 10 ms 27228 KB Output is correct
12 Correct 10 ms 27228 KB Output is correct
13 Correct 52 ms 56912 KB Output is correct
14 Correct 270 ms 65616 KB Output is correct
15 Correct 373 ms 65616 KB Output is correct
16 Correct 251 ms 65648 KB Output is correct
17 Correct 263 ms 65712 KB Output is correct
18 Correct 214 ms 65616 KB Output is correct
19 Correct 1494 ms 158064 KB Output is correct
20 Correct 1837 ms 158420 KB Output is correct