Submission #881937

#	Time	Username	Problem	Language	Result	Execution time	Memory
881937		presko	Beautiful row (IZhO12_beauty)	C++14	0 / 100	1 ms	348 KiB

beauty

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
vector<int> order[33];
vector<int> edges[100];
bool used[100];
int bin(int n)
{
    int cntr=0;
    while(n>0)
    {
        if(n&1)cntr++;
        n>>=1;
    }
    return cntr;
}
int ter(int n)
{
    int cntr=0;
    while(n>0)
    {
        if(n%3==1)cntr++;
        n/=3;
    }
    return cntr;
}
void build(int ind,int b, int t)
{
    for(int i=0;i<(int)order[b].size();i++)
    {
        edges[ind].push_back(order[b][i]);
        edges[order[b][i]].push_back(ind);
    }
    if(b==t)return;
    for(int i=0;i<(int)order[t].size();i++)
    {
        edges[ind].push_back(order[t][i]);
        edges[order[t][i]].push_back(ind);
    }
}
long long dfs(int curr, int cntr, int n, bool used[])
{
    if(cntr==n)return 1;
    long long sum=0;
    for(int i=0;i<(int)edges[curr].size();i++)
    {
        int curr2=edges[curr][i];
        if(used[curr2]==0)
        {
            used[curr2]=1;
            sum+=dfs(curr2,cntr+1,n,used);
            used[curr2]=0;
        }
    }
    return sum;
}
int main()
{
    int n;
    long long ans=0;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int a;
        cin>>a;
        int res1=bin(a);
        int res2=ter(a);
        build(i,res1,res2);
        order[res1].push_back(i);
        if(res1!=res2)order[res2].push_back(i);
        sort(order[res1].begin(),order[res1].end());//speed up with binary search
        sort(order[res2].begin(),order[res2].end());//speed up with binary search
    }

    for(int i=1;i<=n;i++)
    {
        //memset(used,0,95);
        used[i]=1;
        ans+=dfs(i,1,n,used);//node,cntr,n,used[]
        used[i]=0;
    }
    cout<<ans<<"\n";
}

• Subtask 1: 0 / 100