제출 #948976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
948976		vjudge306	아름다운 순열 (IZhO12_beauty)	C++17	100 / 100	770 ms	164512 KiB

beauty

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define nn "\n"
#define x_x ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define intt int _; cin >> _; while (_--)
#define emp push_back
#define mod 1000000007
#define all(v) v.begin(), v.end()
#define ld long double
#define A first
#define B second
//#define int long long
typedef long long ll;
const ld eps = 1e-27;
// diff between decimals 0.000000001 mt19937 mt(time(nullptr));
ll dp[(1<<20)][20];
int main() {

    x_x
    int n; cin>>n; pair<int,int> ar[n];
    for (int i=0; i<n; i++) {
        int x,y; cin>>x; int c=0;
        y=x; while (y) {c+=(y%2); y/=2;}
        ar[i].A=c; c=0;
        y=x; while (y) {c+=(y%3==1); y/=3;}
        ar[i].B=c;

        dp[(1<<i)][i]=1;
    }
    ll to=(1<<n);
    for (int msk=1; msk<to; msk++) {

        for(int ind=0; ind<n; ind++) {
            if (!(msk&(1<<ind))) continue;
            int msk2=(msk^(1<<ind));
        ll x=0;
        for (int j=0; j<n; j++) {
            if (!(msk2&(1<<j))) continue;
            if (ar[ind].A==ar[j].A||ar[ind].B==ar[j].B)
                x+=dp[msk2][j];
        }
        dp[msk][ind]+=x;
        }
    }
    --to; ll ans=0;
    for (int i=0; i<n; i++)
    ans+=dp[to][i];
    cout<<ans;
  return 0;
}

• Subtask 1: 100 / 100