oj.uz

Submission #716435

# Submission time Handle Problem Language Result Execution time Memory
716435 2023-03-30T05:55:29 Z vjudge1 Beautiful row (IZhO12_beauty) C++17
100 / 100
 2531 ms 164556 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 5e5 + 100;
const int mod = (int)1e9+7;
int n;
int a[maxn];
int g[22][22];
ll dp[1<<20][20];

int ter(int x) {
    int cnt = 0;
    while(x > 0) {
        if(x % 3 == 1) cnt++;
        x /= 3;
    }
    return cnt;
}
ll rec(int mask, int last) {
    if(__builtin_popcount(mask) == n) {
        return 1;
    }
    if(dp[mask][last] != -1) return dp[mask][last];
    dp[mask][last] = 0;
    for(int i = 0; i < n; i++) {
        if(g[last][i] && !(mask & (1<<i))) {
            dp[mask][last] += rec(mask|1<<i, i);
        }
    }
    return dp[mask][last];
}
int main() {
    ios_base::sync_with_stdio(false);

    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(__builtin_popcount(a[i]) == __builtin_popcount(a[j])) {
                g[i][j] = 1;
            } else {
                if(ter(a[i]) == ter(a[j])) {
                    g[i][j] = 1;
                }
            }
        }
    }
    memset(dp, -1, sizeof dp);
    ll ans = 0;
    for(int i = 0; i < n; i++) {
        ans += rec(1<<i, i);
    }
    cout << ans << "\n";
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 164428 KB Output is correct
2 Correct 62 ms 164436 KB Output is correct
3 Correct 73 ms 164352 KB Output is correct
4 Correct 63 ms 164392 KB Output is correct
5 Correct 59 ms 164416 KB Output is correct
6 Correct 60 ms 164428 KB Output is correct
7 Correct 59 ms 164376 KB Output is correct
8 Correct 63 ms 164428 KB Output is correct
9 Correct 62 ms 164468 KB Output is correct
10 Correct 65 ms 164412 KB Output is correct
11 Correct 82 ms 164472 KB Output is correct
12 Correct 75 ms 164452 KB Output is correct
13 Correct 147 ms 164468 KB Output is correct
14 Correct 427 ms 164416 KB Output is correct
15 Correct 451 ms 164464 KB Output is correct
16 Correct 298 ms 164556 KB Output is correct
17 Correct 397 ms 164520 KB Output is correct
18 Correct 247 ms 164468 KB Output is correct
19 Correct 2293 ms 164464 KB Output is correct
20 Correct 2531 ms 164468 KB Output is correct