Submission #339112

#	Time	Username	Problem	Language	Result	Execution time	Memory
339112		scales	Beautiful row (IZhO12_beauty)	C++17	100 / 100	1051 ms	164588 KiB

beauty

#include <bits/stdc++.h>
/*#ifndef LOCAL_RUN
    #pragma GCC optimize("Ofast")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("fast-math")
    #pragma GCC target("avx2,tune=native")
#endif*/
using namespace std;
long long dp[20][1100000];
int main()
{
        ios::sync_with_stdio(false);
        cin.tie(0);
        //freopen("b.in","r",stdin);
        //freopen("b.out","w",stdout);
    int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
    long long sum;
    vector<int > d(31),t(21);
    d[0]=1;
    t[0]=1;
    for(i=1;i<=30;i++)
    {
        d[i]=d[i-1]*2;
        //cout<<"d[i]="<<d[i]<<endl;
    }
    for(i=1;i<=18;i++)
    {
        t[i]=t[i-1]*3;
        //cout<<"t["<<i<<"]="<<t[i]<<endl;
    }
    cin>>n;
    vector<int> a(n),b(n),c(n);
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        b[i]=0;
        c[i]=0;
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<=30;j++)
        {
            z=a[i]&d[j];
            if(z!=0)
            {
                b[i]++;
            }
        }
       // cout<<"b["<<i<<"]="<<b[i]<<endl;
    }
    for(i=0;i<n;i++)
    {
        for(j=18;j>=0;j--)
        {
            //cout<<"a["<<i<<"]="<<a[i]<<endl;
            if(a[i]>=2*t[j])
            {
                a[i]=a[i]-2*t[j];
            }
            else
            {
                if(a[i]>=t[j])
                {
                    c[i]++;
                    a[i]=a[i]-t[j];
                }
            }
        }
       // cout<<"c["<<i<<"]="<<c[i]<<endl;
    }
    //cout<<endl;
    int s[20][20];
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(c[i]==c[j] || b[i]==b[j])
            {
                s[i][j]=1;
            }
            else
            {
                s[i][j]=0;
            }
            //cout<<s[i][j]<<" ";
        }
        //cout<<endl;
    }
    for(i=0;i<n;i++)
    {
        dp[i][0]=0;
    }
    for(j=1;j<d[n];j++)
    {
        for(i=0;i<n;i++)
        {
                if(j==d[i])
                {
                    dp[i][j]=1;
                }
                else
                {
                    dp[i][j]=0;
                    z=j&d[i];
                    if(z!=0)
                    {
                        x=j-d[i];
                        //cout<<"x="<<x<<" ";
                        for(q=0;q<n;q++)
                        {
                            if(q!=i && s[q][i]==1)
                            {
                                z=j&d[q];
                                if(z!=0)
                                {
                                    dp[i][j]=dp[i][j]+dp[q][x];
                                }
                            }
                        }
                    }
                }
                //cout<<"dp["<<i<<"]["<<j<<"]="<<dp[i][j]<<endl;
        }
    }
    sum=0;
    for(i=0;i<n;i++)
    {
        sum=sum+dp[i][d[n]-1];
    }
    cout<<sum<<endl;



    return 0;
}

Compilation message (stderr)

beauty.cpp: In function 'int main()':
beauty.cpp:16:13: warning: unused variable 'y' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |             ^
beauty.cpp:16:17: warning: unused variable 'm' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                 ^
beauty.cpp:16:19: warning: unused variable 'k' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                   ^
beauty.cpp:16:21: warning: unused variable 'x1' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                     ^~
beauty.cpp:16:24: warning: unused variable 'g' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                        ^
beauty.cpp:16:26: warning: unused variable 'y1' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                          ^~
beauty.cpp:16:33: warning: unused variable 'f' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                                 ^
beauty.cpp:16:35: warning: unused variable 'l' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                                   ^
beauty.cpp:16:39: warning: unused variable 'maxi' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                                       ^~~~
beauty.cpp:16:44: warning: unused variable 'r' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                                            ^
beauty.cpp:16:46: warning: unused variable 'kol' [-Wunused-variable]
   16 |     int i,j,y,z,m,k,x1,g,y1,n,x,f,l,q,maxi,r,kol;
      |                                              ^~~

• Subtask 1: 100 / 100