oj.uz

Submission #485547

# Submission time Handle Problem Language Result Execution time Memory
485547 2021-11-08T05:53:04 Z ak2006 Beautiful row (IZhO12_beauty) C++14
100 / 100
 1349 ms 172764 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
int main()
{
    setIO();
    int n;
    cin>>n;
    vi a(n),cnt2(n),cnt3(n);
    vvb adj(n,vb(n,false));
    for (int i = 0;i<n;i++){
        cin>>a[i];
        int x = a[i];
        while (x > 0){
            cnt2[i] += (x%2 == 1);
            x /= 2;
        }
        x = a[i];
        while (x > 0){
            cnt3[i] += (x%3 == 1);
            x /= 3;
        }
    }
    
    for (int i = 0;i<n;i++){
        for (int j = 0;j<n;j++){
            if (i == j)continue;
            adj[i][j] = (cnt2[i] == cnt2[j] or 
                cnt3[i] == cnt3[j]);
        }
    }
    
    vvl dp(n,vl(1<<n,0));
    for (int i = 0;i<n;i++)
        dp[i][(1<<i)] = 1;
    
    for (int mask = 0;mask<(1<<n);mask++){
        for (int i = 0;i<n;i++){
            if (!(mask & (1<<i)))continue;
            for (int j = 0;j<n;j++){
                if (!(mask & (1<<j)))
                    assert(dp[j][mask - (1<<i)] == 0);
                if (adj[i][j])
                    dp[i][mask] += 
                        dp[j][mask - (1<<i)];
            }
        }
    }

    ll ans = 0;
    for (int i = 0;i<n;i++)
        ans += dp[i][(1<<n) - 1];
    cout<<ans<<"\n";
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 12 ms 2252 KB Output is correct
12 Correct 10 ms 2252 KB Output is correct
13 Correct 50 ms 9036 KB Output is correct
14 Correct 250 ms 39372 KB Output is correct
15 Correct 288 ms 39504 KB Output is correct
16 Correct 248 ms 39296 KB Output is correct
17 Correct 268 ms 39372 KB Output is correct
18 Correct 259 ms 39372 KB Output is correct
19 Correct 1285 ms 172744 KB Output is correct
20 Correct 1349 ms 172764 KB Output is correct