Submission #83171

# Submission time Handle Problem Language Result Execution time Memory
83171 2018-11-05T19:35:23 Z nikolapesic2802 Beautiful row (IZhO12_beauty) C++14
0 / 100
3000 ms 165080 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(tr==0)
    {
        if(mask==0)
        {
            dp[tr][mask]=1;
        }
        else
        {
            dp[tr][mask]=0;
        }
    }
    if(dp[tr][mask]!=-1)
        return dp[tr][mask];
    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()
{
    memset(dp,-1,sizeof(dp));
    vector<int> connect[32][2];
    int n;
    scanf("%i",&n);
    vector<int> niz(n);
    for(int i=0;i<n;i++)
    {
        scanf("%i",&niz[i]);
        int c2=cnt2(niz[i]);
        int c3=cnt3(niz[i]);
        //printf("%i %i\n",c2,c3);
        connect[c2][0].pb(i);
        //if(c2!=c3)
        connect[c3][1].pb(i);
    }
    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);
            }
        }
        //if(c2!=c3)
            for(auto p:connect[c3][1])
            {
                if(p!=i)
                {
                    //printf("%i -> %i\n",i,p);
                    graf[i].insert(p);
                }
            }
    }
    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)calc(i,tr)*calc(j,inverse);
            }
        }
    }
    for(int i=1;i<n;i++)
    {
        int mask=((1<<n)-1)-(1<<i);
        //printf("%i %i\n",i,mask);
        cnt+=(ll)2*calc(i,mask);
    }
    printf("%lld\n",cnt);
    return 0;
}

Compilation message

beauty.cpp: In function 'int main()':
beauty.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
beauty.cpp:74: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 137 ms 164472 KB Output is correct
2 Correct 138 ms 164604 KB Output is correct
3 Correct 133 ms 164664 KB Output is correct
4 Correct 137 ms 164664 KB Output is correct
5 Correct 130 ms 164664 KB Output is correct
6 Correct 137 ms 164664 KB Output is correct
7 Correct 147 ms 164664 KB Output is correct
8 Correct 132 ms 164664 KB Output is correct
9 Correct 137 ms 164664 KB Output is correct
10 Correct 138 ms 164684 KB Output is correct
11 Correct 143 ms 164704 KB Output is correct
12 Correct 164 ms 164852 KB Output is correct
13 Correct 200 ms 164936 KB Output is correct
14 Correct 601 ms 165048 KB Output is correct
15 Correct 659 ms 165048 KB Output is correct
16 Correct 543 ms 165048 KB Output is correct
17 Correct 577 ms 165080 KB Output is correct
18 Correct 505 ms 165080 KB Output is correct
19 Correct 2863 ms 165080 KB Output is correct
20 Execution timed out 3064 ms 165080 KB Time limit exceeded