oj.uz

Submission #500806

# Submission time Handle Problem Language Result Execution time Memory
500806 2022-01-01T10:12:52 Z SmolBrain Beautiful row (IZhO12_beauty) C++17
100 / 100
 391 ms 205528 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

# Verdict Execution time Memory 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 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 0 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 3404 KB Output is correct
12 Correct 4 ms 3520 KB Output is correct
13 Correct 19 ms 13044 KB Output is correct
14 Correct 96 ms 51612 KB Output is correct
15 Correct 81 ms 51568 KB Output is correct
16 Correct 83 ms 51516 KB Output is correct
17 Correct 89 ms 51524 KB Output is correct
18 Correct 86 ms 51516 KB Output is correct
19 Correct 391 ms 205528 KB Output is correct
20 Correct 382 ms 205424 KB Output is correct