oj.uz

답안 #500807

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
500807 2022-01-01T10:13:25 Z SmolBrain 아름다운 순열 (IZhO12_beauty) C++17
100 / 100
 388 ms 205500 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long int ll;
typedef long double ld;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define endl '\n'
#define pb push_back
#define conts continue
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define ff first
#define ss second
#define ceil2(x,y) ((x+y-1) / y)
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x <<" = "; print(x); cout << endl;
#else
#define debug(x)
#endif

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)

bool iseven(ll n) {if ((n & 1) == 0) return true; return false;}

void print(ll t) {cout << t;}
void print(int t) {cout << t;}
void print(string t) {cout << t;}
void print(char t) {cout << t;}
void print(double t) {cout << t;}
void print(ld t) {cout << t;}

template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(pair <T, V> p) {cout << "{"; print(p.ff); cout << ","; print(p.ss); cout << "}";}
template <class T> void print(vector <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(set <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(multiset <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T, class V> void print(map <T, V> v) {cout << "[ "; for (auto i : v) {print(i); cout << " ";} cout << "]";}

void usaco(string filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")

const int MOD = 1e9 + 7;
const int maxn = 1e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = 1e18 + 5;

bool can[25][25];
ll dp[(1 << 20) + 5][25];

int binaryones(int x) {
    int cnt = 0;
    while (x) {
        cnt += (x & 1);
        x /= 2;
    }

    return cnt;
}

int ternaryones(int x) {
    int cnt = 0;
    while (x) {
        if (x % 3 == 1) cnt++;
        x /= 3;
    }

    return cnt;
}

bool get(int x, int y) {
    if (binaryones(x) == binaryones(y)) return true;
    if (ternaryones(x) == ternaryones(y)) return true;
    return false;
}

void solve(int test_case)
{
    int n; cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];

    rep(i, n) {
        rep(j, n) {
            can[i][j] = get(a[i], a[j]);
        }
    }

    rep(mask, (1 << n)) {
        rep(i, n) {
            int f = 1 << i;
            if ((mask & f) == 0) conts;
            int ind = mask ^ f;

            if (ind == 0) {
                dp[mask][i] = 1;
                conts;
            }

            rep(j, n) {
                if (i == j) conts;
                if (!can[j][i]) conts;

                dp[mask][i] += dp[ind][j];
            }
        }
    }

    ll ans = 0;

    rep(i, n) {
        ans += dp[(1 << n) - 1][i];
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;
    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message

beauty.cpp: In function 'void usaco(std::string)':
beauty.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
beauty.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 0 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 4 ms 3476 KB Output is correct
12 Correct 4 ms 3492 KB Output is correct
13 Correct 16 ms 13132 KB Output is correct
14 Correct 74 ms 51588 KB Output is correct
15 Correct 78 ms 51548 KB Output is correct
16 Correct 71 ms 51596 KB Output is correct
17 Correct 78 ms 51796 KB Output is correct
18 Correct 69 ms 51532 KB Output is correct
19 Correct 360 ms 205484 KB Output is correct
20 Correct 388 ms 205500 KB Output is correct