oj.uz

Submission #683730

# Submission time Handle Problem Language Result Execution time Memory
683730 2023-01-19T08:44:02 Z nifeshe Beautiful row (IZhO12_beauty) C++17
100 / 100
 1060 ms 205644 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC target ("avx2")
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma comment (linker, "/STACK: 16777216")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mp make_pair
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> using oset = tree<T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const ll mod = 998244353;
const ll base = 1e6 + 5;
const ll inf = 1e12;
const int MAX = 2e5 + 5;
const int LG = 20;

random_device rd;
mt19937 gen(rd());
uniform_int_distribution<ll> dis(1, inf);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(auto &i : a) {
        cin >> i;
    }
    vector<int> bin(n), ter(n);
    for(int i = 0; i < n; i++) {
        bin[i] = __builtin_popcount(a[i]);
        int x = a[i];
        while(x) {
            ter[i] += (x % 3 == 1);
            x /= 3;
        }
    }
    vector<vector<int>> go(n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(bin[i] == bin[j] || ter[i] == ter[j]) go[i].pb(j);
        }
    }
    vector<vector<int>> dp((1 << n), vector<int>(n));
    for(int i = 0; i < n; i++) dp[1 << i][i] = 1;
    for(int mask = 1; mask < (1 << n); mask++) {
        for(int lst = 0; lst < n; lst++) {
            if(!dp[mask][lst]) continue;
            for(auto i : go[lst]) {
                if(mask >> i & 1) continue;
                dp[mask | (1 << i)][i] += dp[mask][lst];
            }
        }
    }
    int ans = accumulate(all(dp[(1 << n) - 1]), 0LL);
    cout << ans << '\n';
}

signed main() {
//    freopen("skyline.in", "r", stdin); freopen("skyline.out", "w", stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 9 ms 2772 KB Output is correct
12 Correct 7 ms 2772 KB Output is correct
13 Correct 43 ms 11012 KB Output is correct
14 Correct 193 ms 47560 KB Output is correct
15 Correct 237 ms 47436 KB Output is correct
16 Correct 171 ms 47444 KB Output is correct
17 Correct 208 ms 47528 KB Output is correct
18 Correct 135 ms 47428 KB Output is correct
19 Correct 999 ms 205536 KB Output is correct
20 Correct 1060 ms 205644 KB Output is correct