oj.uz

Submission #312687

# Submission time Handle Problem Language Result Execution time Memory
312687 2020-10-14T05:29:24 Z Trickster Beautiful row (IZhO12_beauty) C++14
100 / 100
 955 ms 246648 KB 
#include <algorithm>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;

#define lm (1<<30)
#define N 30
#define ff first
#define ss second
#define ll long long
#define pb push_back
#define mod 1000000007
#define pii pair <ll, ll>
#define sz(a) int(a.size())
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
ll bigmod(ll a,ll e) {if(e==0)return 1;ll x=bigmod(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int n;
ll ans;
pii p[N];
int v[N];
ll dp[(1<<20)][N];

int main()
{
    scanf("%d", &n);

    for(int i = 0; i < n; i++) {
        scanf("%d", &v[i]);

        int x = v[i], cnt = 0;
        while(x) cnt += x%2, x/=2;

        p[i].ff = cnt;
        x = v[i], cnt = 0;
        while(x) cnt += (x%3 == 1 ? 1 : 0), x/=3;
        p[i].ss = cnt;

        dp[1<<i][i] = 1;
    }

    ll ans = 0;
    for(int i = 1; i < (1<<n); i++)
        for(int h = 0; h < n; h++) {
            int b = (1<<h);

            if(!(b&i)) continue;
            int cur = (1<<h)^(i);

            for(int j = 0; j < n; j++) {
                b = (1<<j);
                if(!(b&cur)) continue;

                if(p[h].ff == p[j].ff || p[h].ss == p[j].ss) dp[i][h] += dp[cur][j];
            }

            if(i == (1<<n)-1) ans += dp[i][h];
        }
    
    printf("%lld", ans);
}

Compilation message

beauty.cpp: In function 'int main()':
beauty.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
beauty.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |         scanf("%d", &v[i]);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 10 ms 4216 KB Output is correct
12 Correct 10 ms 4224 KB Output is correct
13 Correct 45 ms 15736 KB Output is correct
14 Correct 207 ms 61816 KB Output is correct
15 Correct 194 ms 61944 KB Output is correct
16 Correct 212 ms 61944 KB Output is correct
17 Correct 220 ms 61816 KB Output is correct
18 Correct 212 ms 61944 KB Output is correct
19 Correct 955 ms 246648 KB Output is correct
20 Correct 853 ms 246648 KB Output is correct