Submission #83182

# Submission time Handle Problem Language Result Execution time Memory
83182 2018-11-05T22:44:11 Z nikolapesic2802 Beautiful row (IZhO12_beauty) C++14
100 / 100
2919 ms 164820 KB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ll long long
#define pb push_back

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; ///find_by_order(),order_of_key()
vector<set<int> > graf(20);

int cnt2(int n)
{
    int c=0;
    while(n>0)
    {
        if(n%2==1)
            c++;
        n/=2;
    }
    return c;
}
int cnt3(int n)
{
    int c=0;
    while(n>0)
    {
        if(n%3==1)
            c++;
        n/=3;
    }
    return c;
}
ll dp[20][(1<<20)];

ll calc(int tr,int mask)
{
    //printf("Usao za %i %i\n",tr,mask);
    if(dp[tr][mask]!=-1)
        return dp[tr][mask];
    if(tr==0||(mask&(1))==0)
    {
        if(mask==0&&tr==0)
        {
            dp[tr][mask]=1;
            return 1;
        }
        else
        {
            dp[tr][mask]=0;
            return 0;
        }
    }
    dp[tr][mask]=0;
    for(auto p:graf[tr])
    {
        if((1<<p)&mask)
        {
            //printf("Pozivam za %i %i\n",p,1<<p);
            dp[tr][mask]+=calc(p,(1<<p)^mask);
        }
    }
    return dp[tr][mask];
}

int main()
{
    //srand(time(NULL));
    memset(dp,-1,sizeof(dp));
    vector<int> connect[32][2];
    int n;
    scanf("%i",&n);
    vector<int> niz(n);
    //int a=1e9;
    //int r=rand()%a+1;
    bool same=true;
    for(int i=0;i<n;i++)
    {
        //niz[i]=r;
        scanf("%i",&niz[i]);
        int c2=cnt2(niz[i]);
        int c3=cnt3(niz[i]);
        if(i>0&&niz[i]!=niz[i-1])
            same=false;
        //printf("%i %i\n",c2,c3);
        connect[c2][0].pb(i);
        //if(c2!=c3)
        connect[c3][1].pb(i);
    }
    /*if(same)
    {
        ll res=1;
        for(int i=2;i<n;i++)
            res*=(ll)i;
        printf("%lld\n",res);
        return 0;
    }*/
    for(int i=0;i<n;i++)
    {
        int c2=cnt2(niz[i]);
        int c3=cnt3(niz[i]);
        for(auto p:connect[c2][0])
        {
            if(p!=i)
            {
                //printf("%i -> %i\n",i,p);
                graf[i].insert(p);
            }
        }
        for(auto p:connect[c3][1])
        {
            if(p!=i)
            {
                    //printf("%i -> %i\n",i,p);
                graf[i].insert(p);
            }
        }
    }
    //printf("gotov %i\n",clock());
    for(int i=0;i<n;i++)
    {
        for(int m=0;m<(1<<n);m++)
        {
            calc(i,m);
        }
    }
    //printf("Gotov %i\n",clock());
    ll cnt=0;
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            for(int m=0;m<(1<<(n-1));m++)
            {
                //printf("%i\n",m);
                int tr=m;
                tr<<=1;
                tr+=1;
                if(tr&(1<<i)||tr&(1<<j))
                    continue;
                int inverse=((1<<(n))-1)^tr;
                //printf("%inverse!\n",inverse);
                inverse&=((1<<(n))-1)-(1<<i);
                inverse&=((1<<(n))-1)-(1<<j);
                inverse+=1;
                //printf("%i-%i  %i-%i\n",i,tr,j,inverse);
                //if((ll)calc(i,tr)*calc(j,inverse)>0)
                //printf("%lld %lld  %i-%i   %i-%i  %i\n",calc(i,tr),calc(j,inverse),i,tr,j,inverse,((1<<(n-1))-1));
                cnt+=(ll)2*(ll)dp[i][tr]*dp[j][inverse];
            }
        }
    }
    //printf("Gotov2 %i\n",clock());
    for(int i=1;i<n;i++)
    {
        int mask=((1<<n)-1)-(1<<i);
        //printf("%i %i\n",i,mask);
        cnt+=(ll)2*dp[i][mask];
    }
    printf("%lld\n",cnt);
    return 0;
}

Compilation message

beauty.cpp: In function 'int main()':
beauty.cpp:78:10: warning: variable 'same' set but not used [-Wunused-but-set-variable]
     bool same=true;
          ^~~~
beauty.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
beauty.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&niz[i]);
         ~~~~~^~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 130 ms 164472 KB Output is correct
2 Correct 134 ms 164476 KB Output is correct
3 Correct 140 ms 164580 KB Output is correct
4 Correct 134 ms 164628 KB Output is correct
5 Correct 140 ms 164628 KB Output is correct
6 Correct 136 ms 164628 KB Output is correct
7 Correct 137 ms 164740 KB Output is correct
8 Correct 142 ms 164788 KB Output is correct
9 Correct 146 ms 164788 KB Output is correct
10 Correct 130 ms 164788 KB Output is correct
11 Correct 154 ms 164788 KB Output is correct
12 Correct 152 ms 164788 KB Output is correct
13 Correct 227 ms 164788 KB Output is correct
14 Correct 604 ms 164820 KB Output is correct
15 Correct 690 ms 164820 KB Output is correct
16 Correct 581 ms 164820 KB Output is correct
17 Correct 603 ms 164820 KB Output is correct
18 Correct 478 ms 164820 KB Output is correct
19 Correct 2653 ms 164820 KB Output is correct
20 Correct 2919 ms 164820 KB Output is correct