답안 #83177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83177	2018-11-05T22:27:51 Z	nikolapesic2802	아름다운 순열 (IZhO12_beauty)	C++14	0 / 100	3000 ms	164876 KB

beauty

#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||(mask&(1))==0)
    {
        if(mask==0&&tr==0)
        {
            dp[tr][mask]=1;
            return 1;
        }
        else
        {
            dp[tr][mask]=0;
            return 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:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%i",&n);
     ~~~~~^~~~~~~~~
beauty.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%i",&niz[i]);
         ~~~~~^~~~~~~~~~~~~~

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	132 ms	164444 KB	Output is correct
2	Correct	128 ms	164516 KB	Output is correct
3	Correct	131 ms	164532 KB	Output is correct
4	Correct	134 ms	164600 KB	Output is correct
5	Correct	131 ms	164660 KB	Output is correct
6	Correct	128 ms	164660 KB	Output is correct
7	Correct	131 ms	164688 KB	Output is correct
8	Correct	133 ms	164688 KB	Output is correct
9	Correct	128 ms	164688 KB	Output is correct
10	Correct	134 ms	164780 KB	Output is correct
11	Correct	140 ms	164876 KB	Output is correct
12	Correct	145 ms	164876 KB	Output is correct
13	Correct	203 ms	164876 KB	Output is correct
14	Correct	582 ms	164876 KB	Output is correct
15	Correct	615 ms	164876 KB	Output is correct
16	Correct	514 ms	164876 KB	Output is correct
17	Correct	570 ms	164876 KB	Output is correct
18	Correct	504 ms	164876 KB	Output is correct
19	Correct	2767 ms	164876 KB	Output is correct
20	Execution timed out	3068 ms	164876 KB	Time limit exceeded