oj.uz

Submission #636854

# Submission time Handle Problem Language Result Execution time Memory
636854 2022-08-30T10:15:36 Z saayan007 Beautiful row (IZhO12_beauty) C++14
100 / 100
 931 ms 205508 KB 
#include <bits/stdc++.h>
using namespace std;

/* higher types */
typedef int64_t ll;
typedef long double ld;

/* pairs */
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

/* vectors */
typedef vector<int> vi;
typedef vector<ll> vl;

typedef vector<pi> vpi;
typedef vector<pl> vpl;

/* loops */
#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)

/* shortforms */
#define fr first 
#define sc second
#define pb push_back
#define mp make_pair

#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

/* constants */
const ll infl = numeric_limits<int64_t>::max();
const int infi = numeric_limits<int>::max();
const int modi = 1e9 + 7;
const ll modl = 1e9 + 7;

ll three(ll x)
{
    ll ans = 0;
    while(x > 0)
    {
        if(x%3 == 1)
            ++ans;
        x /= 3;
    }
    return ans;
}

void solve()
{
    ll n;
    cin >> n;
    vl a(n), tw(n), th(n);
    fur(i, 0, n-1)
    {
        cin >> a[i];
        tw[i] = __builtin_popcountll(a[i]);
        th[i] = three(a[i]);
    }

    bool adj[n][n];
    fur(i, 0, n-1)
        fur(j, 0, n-1)
            adj[i][j] = (tw[i] == tw[j] || th[i] == th[j]);

    vector<vl> dp((1 << n), vl(n, 0));
    fur(i, 0, n - 1)
        dp[1 << i][i] = 1;
    fur(i, 1, (1 << n) - 1)
    {
        fur(j, 0, n - 1)
        {
            if(!(i&(1<<j)))
                continue;
            fur(k, 0, n - 1)
            {
                if(k == j || !(i & (1 << k)) || !adj[k][j])
                    continue;
                dp[i][j] += dp[i - (1 << j)][k];
            }
        }
    }

    ll ans = 0;
    fur(i, 0, n - 1)
        ans += dp[(1 << n) - 1][i];
    cout << ans << nl;
}

int main() 
{
    ios::sync_with_stdio(0);
    cin.tie(0);

	ll t = 1;
    // cin >> t;
    while(t--)
    {
        solve();
    }
}

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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 10 ms 2688 KB Output is correct
12 Correct 11 ms 2644 KB Output is correct
13 Correct 43 ms 11092 KB Output is correct
14 Correct 207 ms 47520 KB Output is correct
15 Correct 177 ms 47508 KB Output is correct
16 Correct 199 ms 47440 KB Output is correct
17 Correct 208 ms 47504 KB Output is correct
18 Correct 212 ms 47572 KB Output is correct
19 Correct 931 ms 205484 KB Output is correct
20 Correct 811 ms 205508 KB Output is correct