oj.uz

Submission #335374

# Submission time Handle Problem Language Result Execution time Memory
335374 2020-12-12T06:59:21 Z iulia13 Beautiful row (IZhO12_beauty) C++14
100 / 100
 1044 ms 205804 KB 
#include <iostream>
 
using namespace std;
const int doi = (1 << 20);
long long dp[doi][25];
struct ura{
    int a, b;
};
ura v[25];
int main()
{
    int n, i, p2 = 1, p3 = 1, j;
    long long ans = 0;
    cin >> n;
    for (i = 1; i <= 18; i++)
        p3 *= 3;
    p2 = (1 << 30);
    for (i = 0; i < n; i++)
    {
        int nr, cnr;
        cin >> nr;
        cnr = nr;
        int p = p2;
        while (nr)
        {
            if (nr >= p)
            {
                v[i].a++;
                nr -= p;
            }
            p /= 2;
        }
        nr = cnr;
        p = p3;
        while (nr)
        {
            if (nr >= p)
            {
                v[i].b++;
                nr -= p;
            }
            if (nr >= p)
            {nr -= p; v[i].b--;}
            p /= 3;
        }
        dp[(1 << i)][i] = 1;
    }
    for (int mask = 1; mask < (1 << n); mask++)
        for (i = 0; i < n; i++)
            if (mask & (1 << i))
                for (j = 0; j < n; j++)
                    if (i != j && (mask & (1 << j)))
                    {
                        if (v[i].a == v[j].a || v[j].b == v[i].b)
                            dp[mask][i] += dp[mask ^ (1 << i)][j];
                    }
    for (i = 0; i < n; i++)
        ans += dp[(1 << n) - 1][i];
    cout << ans;
    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 492 KB Output is correct
11 Correct 11 ms 3564 KB Output is correct
12 Correct 11 ms 3564 KB Output is correct
13 Correct 47 ms 13164 KB Output is correct
14 Correct 232 ms 51704 KB Output is correct
15 Correct 195 ms 51692 KB Output is correct
16 Correct 234 ms 51692 KB Output is correct
17 Correct 244 ms 51564 KB Output is correct
18 Correct 239 ms 51692 KB Output is correct
19 Correct 1044 ms 205804 KB Output is correct
20 Correct 879 ms 205548 KB Output is correct