oj.uz

Submission #898571

# Submission time Handle Problem Language Result Execution time Memory
898571 2024-01-04T22:23:11 Z n3rm1n Beautiful row (IZhO12_beauty) C++17
100 / 100
 826 ms 205824 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const long long MAXN = 25, MAXMASK = 2e6+10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
long long n, a[MAXN], cnt2[MAXN], cnt3[MAXN];
long long cnt_bin_2(long long x)
{
    long long cnt = 0;
    while(x)
    {
        if(x % 2 == 1)cnt ++;
        x /= 2;
    }
    return cnt;
}
long long cnt_bin_3(long long x)
{
    long long cnt = 0;
    while(x)
    {
        if(x % 3 == 1)cnt ++;
        x /= 3;
    }
    return cnt;
}
long long dp[MAXMASK][MAXN];
void read()
{
    cin >> n;
    for (long long i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        cnt2[i] = cnt_bin_2(a[i]);
        cnt3[i] = cnt_bin_3(a[i]);
    }
}
void solve()
{
    for (long long i = 1; i <= n; ++ i)
        dp[(1 << (i-1))][i] = 1;
    for (long long mask = 1; mask < (1 << n); ++ mask)
    {
        for (long long last = 1; last <= n; ++ last)
        {
            if(((1 << (last-1)) & mask) == 0)continue;
            for (long long j = 1; j <= n; ++ j)
            {
                if(((1 << (j-1)) & mask) != 0)continue;
                if(cnt2[j] != cnt2[last] &&  cnt3[j] != cnt3[last])continue;
                long long newmask = (mask | (1 << (j-1)));
                dp[newmask][j] += dp[mask][last];
            }
        }
    }
    long long ans = 0;
    for (long long i = 1; i <= n; ++ i)
    {
        ans += dp[(1 << n)-1][i];
    }
    /*sort(a+1, a+n+1);
    for (int i = 1; i <= n; ++ i)
    {
        mp[a[i]] ++;
        if(a[i+1] != a[i])
        {
            int del = mp[a[i]];
            for (int j = del; j >= 1; -- j)
                ans /= j;
        }
    }*/
    cout << ans << endl;
}
int main()
{
    speed();
    read();
    solve();
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 500 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 7 ms 4700 KB Output is correct
12 Correct 7 ms 4700 KB Output is correct
13 Correct 32 ms 14996 KB Output is correct
14 Correct 164 ms 51792 KB Output is correct
15 Correct 143 ms 51796 KB Output is correct
16 Correct 165 ms 51892 KB Output is correct
17 Correct 168 ms 51920 KB Output is correct
18 Correct 163 ms 51892 KB Output is correct
19 Correct 826 ms 205796 KB Output is correct
20 Correct 678 ms 205824 KB Output is correct