# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
91810 | SamAnd | Beautiful row (IZhO12_beauty) | C++17 | 2351 ms | 132816 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N=20;
int n;
int a[N];
pair<int,int> t[N];
vector<int> v[N+1];
long long b[N][1<<N];
int q2(int x)
{
int res=0;
while(x)
{
if(x%2==1)
res++;
x/=2;
}
return res;
}
int q3(int x)
{
int res=0;
while(x)
{
if(x%3==1)
res++;
x/=3;
}
return res;
}
void st(int i)
{
t[i].first=q2(a[i]);
t[i].second=q3(a[i]);
}
bool stg(int i,int j)
{
return (t[i].first==t[j].first || t[i].second==t[j].second);
}
int main()
{
//freopen("b.in","r",stdin);
//freopen("b.out","w",stdout);
cin>>n;
for(int i=0;i<n;++i)
cin>>a[i];
for(int i=0;i<n;++i)
st(i);
for(int i=0;i<(1<<n);++i)
{
v[q2(i)].push_back(i);
}
for(int i=0;i<n;++i)
{
b[i][(1<<i)]=1;
}
for(int ii=2;ii<=n;++ii)
{
for(int i=0;i<n;++i)
{
for(int j=0;j<n;++j)
{
if(!stg(i,j))
continue;
for(int k=0;k<v[ii-1].size();++k)
{
int x=v[ii-1][k];
if((x|(1<<i))!=x)
b[i][x|(1<<i)]+=b[j][x];
}
}
}
}
long long ans=0;
for(int i=0;i<n;++i)
{
ans+=b[i][(1<<n)-1];
}
cout<<ans<<endl;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |