oj.uz

Submission #486292

# Submission time Handle Problem Language Result Execution time Memory
486292 2021-11-11T08:02:27 Z Sho10 Beautiful row (IZhO12_beauty) C++17
100 / 100
 1621 ms 127680 KB 
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho
#define ll long long
#define double long double
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define aint(a) (a).begin(), (a).end()
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 998244353
#define PI 3.14159265359
#define INF 1000000005
#define LINF 1000000000000000005ll
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,check[25][25],dp[25][2000005],a[25],cnt[3][25];
int32_t main(){
CODE_START;
cin>>n;
for(ll i=0;i<n;i++)
{
    cin>>a[i];
}
for(ll i=0;i<n;i++)
{
    ll x=a[i];
    while(x>0){
        if(x%2==1){
            cnt[1][i]++;
        }
        x/=2;
    }
    x=a[i];
    while(x>0){
        if(x%3==1){
            cnt[2][i]++;
        }
        x/=3;
    }
}
for(ll i=0;i<n;i++)
{
    for(ll j=0;j<n;j++)
    {
if(i!=j){
    if(cnt[2][i]==cnt[2][j]){
        check[i][j]=1;
        check[j][i]=1;
    }else if(cnt[1][i]==cnt[1][j]){
    check[i][j]=1;
    check[j][i]=1;
    }
}
    }
}
for(ll i=0;i<n;i++)
{
    dp[i][(1ll<<(i))]=1;
}
for(ll mask=0;mask<(1ll<<n);mask++)
{
for(ll i=0;i<n;i++)
{
    for(ll j=0;j<n;j++)
    {
        if(i==j){
            continue;
        }
        if((1ll<<i)&mask==0){
            continue;
        }
        if((1ll<<(j))&mask){
            if(dp[i][mask-(1ll<<(j))]==0){
                continue;
            }
            if(check[i][j]==0){
                continue;
            }

            dp[j][mask]+=dp[i][mask-(1ll<<(j))];
        }
    }
}
}
ll ans=0;
for(ll i=0;i<n;i++)
{
    ans+=dp[i][(1ll<<(n))-1];
  //  cout<<dp[i][(1ll<<(n))-1]<<' ';
}
cout<<ans<<endl;
}

Compilation message

beauty.cpp: In function 'int32_t main()':
beauty.cpp:73:25: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   73 |         if((1ll<<i)&mask==0){
      |                     ~~~~^~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 448 KB Output is correct
10 Correct 1 ms 400 KB Output is correct
11 Correct 14 ms 1996 KB Output is correct
12 Correct 14 ms 1868 KB Output is correct
13 Correct 71 ms 7428 KB Output is correct
14 Correct 344 ms 30084 KB Output is correct
15 Correct 308 ms 30056 KB Output is correct
16 Correct 355 ms 30080 KB Output is correct
17 Correct 359 ms 30116 KB Output is correct
18 Correct 343 ms 30216 KB Output is correct
19 Correct 1621 ms 127620 KB Output is correct
20 Correct 1465 ms 127680 KB Output is correct