Submission #339110

#TimeUsernameProblemLanguageResultExecution timeMemory
339110fixikmilaBeautiful row (IZhO12_beauty)C++14
100 / 100
777 ms164544 KiB
#include <bits/stdc++.h> using namespace std; #define MOD 1000000007 typedef long long ll; typedef pair<ll,ll>pll; typedef long double ld; ll bin_pow(ll a,ll b){ if(b==0)return 1; if(b%2==0){ ll t=bin_pow(a,b/2); return t*t%MOD; } else return a*bin_pow(a,b-1)%MOD; } vector<ll>graph[20]; bool tr(ll x,ll y){ string s="",s1=""; while(x){ s+=x%3+'0'; x/=3; } while(y){ s1+=y%3+'0'; y/=3; } x=y=0; for(auto u : s){ if(u=='1')x++; } for(auto u : s1){ if(u=='1')y++; } return x==y; } ll dp[1<<20][20]; int main() { //freopen("b.in","r",stdin); //freopen("b.out","w",stdout); ios::sync_with_stdio(false); cin.tie(0); ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN; cin>>n; vector<ll>a(n); map<ll,ll>mp; for(int i=0;i<n;i++)cin>>a[i],mp[a[i]]=x,x++; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ if((__builtin_popcount(a[i])==__builtin_popcount(a[j]))||tr(a[i],a[j])){ //cout<<i<<" "<<j<<endl; graph[i].push_back(j); graph[j].push_back(i); } } } for(int i=1;i<(1<<n);i++){ for(int j=0;j<n;j++){ if((i&(1<<j))!=0){ if(__builtin_popcount(i)==1)dp[i][j]=1; else{ for(auto z : graph[j]){ if((i&(1<<z))!=0){ dp[i][j]+=dp[(i^(1<<j))][z]; } } } } else dp[i][j]=0; } } for(int i=0;i<n;i++){ ans+=dp[(1<<n)-1][i]; } cout<<ans; return 0; }

Compilation message (stderr)

beauty.cpp: In function 'int main()':
beauty.cpp:42:8: warning: unused variable 't' [-Wunused-variable]
   42 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |        ^
beauty.cpp:42:14: warning: unused variable 'm' [-Wunused-variable]
   42 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |              ^
beauty.cpp:42:16: warning: unused variable 'k' [-Wunused-variable]
   42 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                ^
beauty.cpp:42:20: warning: unused variable 'sum' [-Wunused-variable]
   42 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                    ^~~
beauty.cpp:42:26: warning: unused variable 'l' [-Wunused-variable]
   42 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                          ^
beauty.cpp:42:30: warning: unused variable 'r' [-Wunused-variable]
   42 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                              ^
beauty.cpp:42:38: warning: unused variable 'y' [-Wunused-variable]
   42 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                      ^
beauty.cpp:42:42: warning: unused variable 'z' [-Wunused-variable]
   42 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                          ^
beauty.cpp:42:52: warning: unused variable 'mn' [-Wunused-variable]
   42 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                                    ^~
beauty.cpp:42:65: warning: unused variable 'mx' [-Wunused-variable]
   42 |     ll t=1,n,m,k=0,sum=0,l=0,r=0,x=0,y=0,z=0,ans=0,mn=LLONG_MAX,mx=LLONG_MIN;
      |                                                                 ^~
#Verdict Execution timeMemoryGrader output
Fetching results...