oj.uz

답안 #339453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339453 2020-12-25T10:40:49 Z Vladikus004 아름다운 순열 (IZhO12_beauty) C++14
0 / 100
 90 ms 164588 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma target("tune=native")
#pragma GCC target("avx2")
#define mp make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define inf 2e9
#define ff first
#define ss second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;

const int N = 20;
vector <short int> v[N];
short int n;
int a[N];
short int c1[N], c2[N];

void get_cnt(int x, int ind){
    int _c1 = 0, _c2 = 0;
    int X = x;
    while (x){
        if (x % 2 == 1) _c1++;
        x>>=1;
    }
    x = X;
    while (x){
        if (x % 3 == 1) _c2++;
        x /= 3;
    }
    c1[ind] = _c1;
    c2[ind] = _c2;
    return;
}

ll dp[(1<<20)][20];

ll get_dp(int mask, short int lst){
    if (mask == ((1<<n)-1)) return 1;
    if (dp[mask][lst] != -1)
        return dp[mask][lst];
    ll ans = 0;
    for (auto u: v[lst]){
        if (mask & (1<<u)) continue;
        ans += get_dp(mask | (1<<u), u);
    }
    return dp[mask][lst] = ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
//    freopen("input.txt", "r", stdin);
    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++)
        get_cnt(a[i], i);
    for (int i = 0; i < n; i++){
        for (int j = i+1; j < n; j++){
            if (c1[i]==c1[j]||c2[i]==c2[j]){
                v[i].pb(j);
                v[j].pb(i);
            }
        }
    }
    ll ans = 0;
    memset(dp, -1, sizeof dp);
    for (int i = 0; i < n; i++){
        ans += get_dp((1<<i), i);
    }
    cout << ans;
    return 0;
}

Compilation message

beauty.cpp: In function 'int main()':
beauty.cpp:58:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   58 |     freopen("b.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
beauty.cpp:59:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   59 |     freopen("b.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 100.0

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