oj.uz

Submission #679205

# Submission time Handle Problem Language Result Execution time Memory
679205 2023-01-07T17:22:44 Z pragmatist Beautiful row (IZhO12_beauty) C++17
100 / 100
 836 ms 164464 KB 
#include<bits/stdc++.h>
 
#define sz(v) (int)v.size()
#define ll long long
#define pb push_back
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define nl "\n"

using namespace std;
using pii = pair<int, int>;

const int N = (int)3e5 + 7; // make sure this is right
const int M = (int)1e6 + 7;
const int inf = (int)1e9 + 7;
const ll INF = (ll)3e18 + 7; 
const ll MOD = (ll)998244353; // make sure this is right

bool bit(int x, int i) {
	return x >> i & 1;
}

int sum(int x, int y) {
	x += y;
	if(x >= MOD) x -= MOD;
	return x;
}

pii dir[] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

int n, b[20], c[20];
ll dp[1 << 20][20];

void solve() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
    	int x;
    	cin >> x;
    	b[i] = __builtin_popcount(x);
    	while(x) {
    		c[i] += (x % 3 == 1);
    		x /= 3;
    	}
    }

    for(int i = 0; i < n; ++i) dp[1 << i][i] = 1;
    for(int mask = 1; mask < (1 << n); ++mask) {
        for(int i = 0; i < n; ++i) {
            if(bit(mask, i)) {
            	for(int j = 0; j < n; ++j) {
            		if(!bit(mask, j) && (c[i] == c[j] || b[i] == b[j])) {
            			dp[mask | (1 << j)][j] += dp[mask][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(0);
	cin.tie(0);
	int test = 1;
	//cin >> test;
	for(int i = 1; i <= test; ++i) {
	 	//cout << "Case #" << i << ": ";
		solve();
	}
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 9 ms 2892 KB Output is correct
12 Correct 8 ms 2772 KB Output is correct
13 Correct 48 ms 10588 KB Output is correct
14 Correct 177 ms 41304 KB Output is correct
15 Correct 173 ms 41252 KB Output is correct
16 Correct 180 ms 41336 KB Output is correct
17 Correct 181 ms 41356 KB Output is correct
18 Correct 178 ms 41284 KB Output is correct
19 Correct 836 ms 164464 KB Output is correct
20 Correct 816 ms 164448 KB Output is correct