oj.uz

Submission #516812

# Submission time Handle Problem Language Result Execution time Memory
516812 2022-01-22T07:04:59 Z Be_dos Beautiful row (IZhO12_beauty) C++17
0 / 100
 9 ms 1344 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;
            }
        }
    }

    int32_t** dp = new int32_t*[1 << n];
    for(int32_t i = 1; i < (1 << n); i++) {
        dp[i] = new int32_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];
            }
    }

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

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 292 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 292 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Incorrect 9 ms 1344 KB Output isn't correct
12 Halted 0 ms 0 KB -