oj.uz

Submission #516815

# Submission time Handle Problem Language Result Execution time Memory
516815 2022-01-22T07:06:21 Z Be_dos Beautiful row (IZhO12_beauty) C++17
100 / 100
 903 ms 189020 KB 
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
#include <cassert>

int main() {
    int32_t n;
    std::cin >> n;

    int32_t* arr = new int32_t[n];
    for(int32_t i = 0; i < n; i++)
        std::cin >> arr[i];

    bool** graph = new bool*[n];
    for(int32_t i = 0; i < n; i++) {
        graph[i] = new bool[n];
        for(int32_t j = 0; j < n; j++) {
            if(i == j)
                graph[i][j] = false;
            else {
                graph[i][j] = __builtin_popcount(arr[i]) == __builtin_popcount(arr[j]);
                int32_t ones1 = 0;
                int32_t cur = arr[i];
                while(cur > 0) {
                    ones1 += (cur % 3) % 2;
                    cur /= 3;
                }
                int32_t ones2 = 0;
                cur = arr[j];
                while(cur > 0) {
                    ones2 += (cur % 3) % 2;
                    cur /= 3;
                }
                graph[i][j] = graph[i][j] || ones1 == ones2;
            }
        }
    }

    int64_t** dp = new int64_t*[1 << n];
    for(int32_t i = 1; i < (1 << n); i++) {
        dp[i] = new int64_t[n];
        for(int32_t j = 0 ;j < n; j++)
            dp[i][j] = 0;
        if(__builtin_popcount(i) == 1) {
            dp[i][31 - __builtin_clz(i)] = 1;
            continue;
        }

        for(int32_t j = 0; j < n; j++)
            if(i & (1 << j)) {
                for(int32_t k = 0; k < n; k++)
                    if((i & (1 << k)) > 0 && j != k && graph[j][k])
                        dp[i][j] += dp[i ^ (1 << j)][k];
            }
    }

    int64_t ans = 0;
    for(int32_t i = 0; i < n; i++)
        ans += dp[(1 << n) - 1][i];
    std::cout << ans;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 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 9 ms 2368 KB Output is correct
12 Correct 9 ms 2464 KB Output is correct
13 Correct 38 ms 10024 KB Output is correct
14 Correct 201 ms 43324 KB Output is correct
15 Correct 160 ms 43332 KB Output is correct
16 Correct 189 ms 43328 KB Output is correct
17 Correct 203 ms 43332 KB Output is correct
18 Correct 195 ms 43328 KB Output is correct
19 Correct 903 ms 189012 KB Output is correct
20 Correct 765 ms 189020 KB Output is correct