oj.uz

답안 #881936

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881936 2023-12-02T09:59:08 Z presko 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
 0 ms 348 KB 
#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<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<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<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";
}

Compilation message

beauty.cpp: In function 'void build(int, int, int)':
beauty.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i=0;i<order[b].size();i++)
      |                 ~^~~~~~~~~~~~~~~~
beauty.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0;i<order[t].size();i++)
      |                 ~^~~~~~~~~~~~~~~~
beauty.cpp: In function 'long long int dfs(int, int, int, bool*)':
beauty.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<edges[curr].size();i++)
      |                 ~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -