oj.uz

Submission #483242

# Submission time Handle Problem Language Result Execution time Memory
483242 2021-10-28T10:51:01 Z dxz05 Beautiful row (IZhO12_beauty) C++14
100 / 100
 2200 ms 205596 KB 
#pragma GCC optimize("Ofast,O2,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define lla(x) (x).rbegin(), (x).rend()

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

#define MP make_pair

typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.000001;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 1e6 + 3e2;
const int M = 222;

bool can(int x, int y){
    if (__builtin_popcount(x) == __builtin_popcount(y)) return true;
    int res = 0;
    while (x > 0 || y > 0){
        res += x % 3 == 1;
        res -= y % 3 == 1;
        x /= 3;
        y /= 3;
    }
    return res == 0;
}


int a[N];
void solve(int TC) {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) cin >> a[i];

    vector<vector<ll>> dp(1 << n, vector<ll>(n, 0ll));

    for (int i = 0; i < n; i++){
        dp[1 << i][i] = 1;
//        for (int j = 0; j < n; j++) cout << can(a[i], a[j]) << ' '; cout << endl;
    }

    for (int mask = 1; mask < (1 << n); mask++){
        for (int i = 0; i < n; i++){
            if (!(mask & (1 << i)) || dp[mask][i] == 0) continue;
            for (int j = 0; j < n; j++){
                if ((mask & (1 << j)) || !can(a[i], a[j])) continue;

                debug(mask, i, j);

                dp[mask | (1 << j)][j] += dp[mask][i];
            }
        }

    }

//    for (auto x : dp){
//        for (auto y : x) cout << y << ' ';
//        cout << endl;
//    }

    cout << accumulate(all(dp.back()), 0ll);

}

int main() {
    startTime = clock();
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int TC = 1;
//    cin >> TC;

    for (int test = 1; test <= TC; test++) {
        //debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

    cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;

    return 0;
}

Compilation message

beauty.cpp: In function 'void solve(int)':
beauty.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
beauty.cpp:76:17: note: in expansion of macro 'debug'
   76 |                 debug(mask, i, j);
      |                 ^~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 11 ms 2764 KB Output is correct
12 Correct 11 ms 2764 KB Output is correct
13 Correct 59 ms 11096 KB Output is correct
14 Correct 357 ms 47436 KB Output is correct
15 Correct 154 ms 47460 KB Output is correct
16 Correct 416 ms 47552 KB Output is correct
17 Correct 439 ms 47512 KB Output is correct
18 Correct 440 ms 47528 KB Output is correct
19 Correct 2200 ms 205436 KB Output is correct
20 Correct 777 ms 205596 KB Output is correct