oj.uz

답안 #531031

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
531031 2022-02-27T12:18:53 Z Homichki 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
 3000 ms 82996 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll dp[1<<20+1][21];
ll st3(ll x)
{
    ll kol=0;
    while(x>0)
    {
        if(x%3==1)
        {
            kol++;
        }
        x/=3;
    }
    return kol;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //ifstream cin("b.in");
    //ofstream cout("b.out");
    ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
    vector<ll> a,b,st(21);
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>x;
        a.push_back(x);
    }
    st[0]=1;
    for(i=1;i<21;i++)
    {
        st[i]=st[i-1]*2;
    }
    for(i=0;i<n;i++)
    {
        dp[st[i]][i]=1;
    }
    for(mask=1;mask<st[n];mask++)
    {
        y=__builtin_popcount(mask);
        if(y>1)
        {
            for(j=0;j<n;j++)
            {
                y=mask&st[j];
                if(y>0)
                {
                    for(q=0;q<n;q++)
                    {
                        x=mask&st[q];
                        if((x>0) && (q!=j))
                        {
                            z=__builtin_popcount(a[q]);
                            y=st3(a[q]);
                            z1=__builtin_popcount(a[j]);
                            y1=st3(a[j]);
                            if((y1==y) || (z==z1))
                            {
                                dp[mask][j]+=dp[mask-st[j]][q];
                            }
                        }
                    }
                }
            }
        }
    }
    sum=0;
    for(i=0;i<n;i++)
    {
        sum+=dp[st[n]-1][i];
    }
    cout<<sum;
    return 0;
}

Compilation message

beauty.cpp:5:12: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | ll dp[1<<20+1][21];
      |          ~~^~
beauty.cpp: In function 'int main()':
beauty.cpp:25:8: warning: unused variable 'ma' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |        ^~
beauty.cpp:25:11: warning: unused variable 'qqq' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |           ^~~
beauty.cpp:25:17: warning: unused variable 'kot' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                 ^~~
beauty.cpp:25:23: warning: unused variable 'l' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                       ^
beauty.cpp:25:25: warning: unused variable 'r' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                         ^
beauty.cpp:25:29: warning: unused variable 'kry' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                             ^~~
beauty.cpp:25:33: warning: unused variable 'w' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                 ^
beauty.cpp:25:35: warning: unused variable 't' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                   ^
beauty.cpp:25:37: warning: unused variable 'm' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                     ^
beauty.cpp:25:39: warning: unused variable 'k' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                       ^
beauty.cpp:25:41: warning: unused variable 'p' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                         ^
beauty.cpp:25:43: warning: unused variable 'mi' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                           ^~
beauty.cpp:25:52: warning: unused variable 's' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                                    ^
beauty.cpp:25:58: warning: unused variable 'kol' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                                          ^~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 2 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 65 ms 2892 KB Output is correct
12 Correct 74 ms 3024 KB Output is correct
13 Correct 315 ms 11076 KB Output is correct
14 Correct 1644 ms 43332 KB Output is correct
15 Correct 1684 ms 43452 KB Output is correct
16 Correct 1563 ms 43308 KB Output is correct
17 Correct 1520 ms 43320 KB Output is correct
18 Correct 1563 ms 43388 KB Output is correct
19 Execution timed out 3085 ms 82996 KB Time limit exceeded
20 Halted 0 ms 0 KB -