oj.uz

Submission #873870

# Submission time Handle Problem Language Result Execution time Memory
873870 2023-11-16T02:25:26 Z noiaint Beautiful row (IZhO12_beauty) C++17
100 / 100
 1578 ms 158096 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 4696 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 18780 KB Output is correct
7 Correct 2 ms 18908 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 2 ms 18780 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 11 ms 27228 KB Output is correct
12 Correct 11 ms 27228 KB Output is correct
13 Correct 45 ms 56960 KB Output is correct
14 Correct 186 ms 65536 KB Output is correct
15 Correct 240 ms 65616 KB Output is correct
16 Correct 218 ms 65728 KB Output is correct
17 Correct 217 ms 65708 KB Output is correct
18 Correct 189 ms 65676 KB Output is correct
19 Correct 1347 ms 158096 KB Output is correct
20 Correct 1578 ms 158076 KB Output is correct