Submission #1177328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177328		badge881	아름다운 순열 (IZhO12_beauty)	C++20	100 / 100	812 ms	172868 KiB

beauty

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    ll nbNumbers;
    scanf("%lld", &nbNumbers);
    vector<ll> numbers(nbNumbers);
    for (auto &&number : numbers)
        scanf("%lld", &number);
    

    vector<ll> binDecomp(nbNumbers), terDecomp(nbNumbers);
    for (int i = 0; i < nbNumbers; i++)
    {
        ll x = numbers[i];
        while (x)
        {
            binDecomp[i] += x % 2; // or == 1 
            x /= 2;
        }
        x = numbers[i];
        while (x)
        {
            terDecomp[i] += (x % 3 == 1);
            x /= 3;
        }
    }
    vector<vector<ll>> DP(nbNumbers, vector<ll>(1 << nbNumbers));
    for (int i = 0; i < nbNumbers; i++)
        DP[i][(1 << i)] = 1;
    
    for (int i = 0; i < (1 << nbNumbers); i++)
    {
        for (int j = 0; j < nbNumbers; j++)
        {
            if (DP[j][i] == 0)
                continue;
            for (int k = 0; k < nbNumbers; k++)
            {
                if (i & (1 << k))
                    continue;
                if (binDecomp[j] == binDecomp[k] || terDecomp[j] == terDecomp[k])
                    DP[k][i | (1 << k)] += DP[j][i];
            }
        }
    }
    ll ans = 0;
    for (ll i = 0; i < nbNumbers; i++)
        ans += DP[i][(1 << nbNumbers) - 1];
    printf("%lld\n", ans);
}

Compilation message (stderr)

beauty.cpp: In function 'int main()':
beauty.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%lld", &nbNumbers);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~
beauty.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         scanf("%lld", &number);
      |         ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100