답안 #83177

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83177 2018-11-05T22:27:51 Z nikolapesic2802 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
3000 ms 164876 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||(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]);
         ~~~~~^~~~~~~~~~~~~~
# 결과 실행 시간 메모리 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