oj.uz

Submission #346395

# Submission time Handle Problem Language Result Execution time Memory
346395 2021-01-09T14:05:17 Z nicolaalexandra Beautiful row (IZhO12_beauty) C++14
100 / 100
 853 ms 172940 KB 
#include <bits/stdc++.h>
#define DIM 1048580
#define DIMN 21
using namespace std;

long long dp[DIM][DIMN];
int f[DIMN],p[DIMN],v[DIMN];
vector <int> L[DIMN];
int n,i,j;

int countt (int x){

    memset (f,0,sizeof f);

    while (x){
        int p = 1, exp = 0;
        while (p * 3 <= x){
            p *= 3;
            exp++;
        }

        f[exp]++;
        x -= p;
    }

    int sol = 0;
    for (int i=0;i<=19;i++)
        if (f[i] == 1)
            sol++;

    return sol;

}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n;
    for (i=1;i<=n;i++)
        cin>>v[i];

    p[0] = 1;
    for (i=1;i<=19;i++)
        p[i] = p[i-1] * 3;

    for (i=1;i<=n;i++)
        for (j=i+1;j<=n;j++){
            if (__builtin_popcount(v[i]) == __builtin_popcount(v[j]) || countt(v[i]) == countt(v[j])){
                L[i].push_back(j);
                L[j].push_back(i);
                //cout<<i<<" "<<j<<"\n";
            }
        }

    for (i=1;i<=n;i++)
        dp[(1<<(i-1))][i] = 1;

    for (int mask=1;mask<(1<<n);mask++){
        if (__builtin_popcount(mask) <= 1)
            continue;

        for (i=1;i<=n;i++){
            if (!(mask&(1<<(i-1))))
                continue;

            for (auto vecin : L[i]){
                if (!(mask&(1<<(vecin-1))))
                    continue;

                dp[mask][i] += dp[mask-(1<<(i-1))][vecin];

            }}}

    long long sol = 0;
    for (i=1;i<=n;i++)
        sol += dp[(1<<n)-1][i];

    cout<<sol;

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 9 ms 3052 KB Output is correct
12 Correct 9 ms 3052 KB Output is correct
13 Correct 40 ms 11116 KB Output is correct
14 Correct 184 ms 43372 KB Output is correct
15 Correct 190 ms 43392 KB Output is correct
16 Correct 161 ms 43372 KB Output is correct
17 Correct 174 ms 43372 KB Output is correct
18 Correct 134 ms 43520 KB Output is correct
19 Correct 825 ms 172744 KB Output is correct
20 Correct 853 ms 172940 KB Output is correct