oj.uz

Submission #339457

# Submission time Handle Problem Language Result Execution time Memory
339457 2020-12-25T10:41:38 Z Vladikus004 Beautiful row (IZhO12_beauty) C++14
100 / 100
 2778 ms 164588 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma target("tune=native")
#pragma GCC target("avx2")
#define mp make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define inf 2e9
#define ff first
#define ss second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const int N = 20;
vector <short int> v[N];
short int n;
int a[N];
short int c1[N], c2[N];

void get_cnt(int x, int ind){
    int _c1 = 0, _c2 = 0;
    int X = x;
    while (x){
        if (x % 2 == 1) _c1++;
        x>>=1;
    }
    x = X;
    while (x){
        if (x % 3 == 1) _c2++;
        x /= 3;
    }
    c1[ind] = _c1;
    c2[ind] = _c2;
    return;
}

ll dp[(1<<20)][20];

ll get_dp(int mask, short int lst){
    if (mask == ((1<<n)-1)) return 1;
    if (dp[mask][lst] != -1)
        return dp[mask][lst];
    ll ans = 0;
    for (auto u: v[lst]){
        if (mask & (1<<u)) continue;
        ans += get_dp(mask | (1<<u), u);
    }
    return dp[mask][lst] = ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("input.txt", "r", stdin);
  
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++)
        get_cnt(a[i], i);
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++){
            if (c1[i]==c1[j]||c2[i]==c2[j]){
                v[i].pb(j);
                v[j].pb(i);
            }
        }
    }
    ll ans = 0;
    memset(dp, -1, sizeof dp);
    for (int i = 0; i < n; i++){
        ans += get_dp((1<<i), i);
    }
    cout << ans;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 164460 KB Output is correct
2 Correct 84 ms 164460 KB Output is correct
3 Correct 86 ms 164460 KB Output is correct
4 Correct 89 ms 164588 KB Output is correct
5 Correct 86 ms 164460 KB Output is correct
6 Correct 90 ms 164460 KB Output is correct
7 Correct 87 ms 164460 KB Output is correct
8 Correct 85 ms 164460 KB Output is correct
9 Correct 85 ms 164460 KB Output is correct
10 Correct 85 ms 164460 KB Output is correct
11 Correct 93 ms 164460 KB Output is correct
12 Correct 93 ms 164588 KB Output is correct
13 Correct 147 ms 164460 KB Output is correct
14 Correct 449 ms 164460 KB Output is correct
15 Correct 563 ms 164460 KB Output is correct
16 Correct 366 ms 164460 KB Output is correct
17 Correct 482 ms 164460 KB Output is correct
18 Correct 287 ms 164460 KB Output is correct
19 Correct 2503 ms 164552 KB Output is correct
20 Correct 2778 ms 164588 KB Output is correct