oj.uz

Submission #91810

# Submission time Handle Problem Language Result Execution time Memory
91810 2018-12-30T07:28:49 Z SamAnd Beautiful row (IZhO12_beauty) C++17
100 / 100
 2351 ms 132816 KB 
#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

beauty.cpp: In function 'int main()':
beauty.cpp:71:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int k=0;k<v[ii-1].size();++k)
                             ~^~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 476 KB Output is correct
11 Correct 10 ms 2040 KB Output is correct
12 Correct 10 ms 2040 KB Output is correct
13 Correct 46 ms 7676 KB Output is correct
14 Correct 305 ms 31464 KB Output is correct
15 Correct 375 ms 31588 KB Output is correct
16 Correct 257 ms 31468 KB Output is correct
17 Correct 310 ms 31724 KB Output is correct
18 Correct 222 ms 31596 KB Output is correct
19 Correct 1840 ms 132684 KB Output is correct
20 Correct 2351 ms 132816 KB Output is correct