#include <cstdint> #include <cstdio> #include <cstdlib> #include <algorithm> #include <limits> #include <numeric> #include <vector> struct histogram_part_t { uint64_t inversions; uint64_t count; }; using histogram_t = std::vector<histogram_part_t>; using permutation_t = std::vector<int>; permutation_t read_input() { permutation_t perm; int n; (void)scanf("%d", &n); perm.reserve(n); for (int i = 0; i < n; i++) { int x; (void)scanf("%d", &x); perm.push_back(x - 1); } return perm; } // An exponential algorithm // O(n * 2^n) histogram_t compute_histogram(const permutation_t permutation) { histogram_t ret; ret.resize(permutation.size() + 1, histogram_part_t{std::numeric_limits<uint64_t>::max(), 0}); std::vector<uint64_t> inversions; inversions.reserve(permutation.size()); inversions.push_back(0); // Pre-compute inversions for (unsigned int i = 1; i < permutation.size(); i++) { uint64_t mask = 0; for (unsigned int j = 0; j < i; j++) { if (permutation[j] > permutation[i]) { mask |= (uint64_t)1 << (uint64_t)j; } } inversions.push_back(mask); } // For each subset of the permutation, compute the best inversion count for (uint64_t subset = 0; subset < (uint64_t)1 << (uint64_t)permutation.size(); subset++) { uint64_t invs_for_set = 0; for (unsigned int i = 1; i < inversions.size(); i++) { if (subset & ((uint64_t)1 << (uint64_t)i)) { invs_for_set += __builtin_popcountll(subset & inversions[i]); } } const int idx = __builtin_popcountll(subset); ret[idx].inversions = std::min(ret[idx].inversions, invs_for_set); } // Now that we have the best counts, we can count the best subsets for (uint64_t subset = 0; subset < (uint64_t)1 << (uint64_t)permutation.size(); subset++) { uint64_t invs_for_set = 0; for (unsigned int i = 1; i < inversions.size(); i++) { if (subset & ((uint64_t)1 << (uint64_t)i)) { invs_for_set += __builtin_popcountll(subset & inversions[i]); } } const int idx = __builtin_popcountll(subset); if (ret[idx].inversions == invs_for_set) { ret[idx].count++; } } return ret; } void print_histogram(const histogram_t histogram) { for (unsigned int i = 1; i < histogram.size(); i++) { printf("%llu %llu\n", (unsigned long long int)histogram[i].inversions, (unsigned long long int)histogram[i].count); } } int main() { const auto perm = read_input(); const auto histogram = compute_histogram(std::move(perm)); print_histogram(std::move(histogram)); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 | #include <cstdint> #include <cstdio> #include <cstdlib> #include <algorithm> #include <limits> #include <numeric> #include <vector> struct histogram_part_t { uint64_t inversions; uint64_t count; }; using histogram_t = std::vector<histogram_part_t>; using permutation_t = std::vector<int>; permutation_t read_input() { permutation_t perm; int n; (void)scanf("%d", &n); perm.reserve(n); for (int i = 0; i < n; i++) { int x; (void)scanf("%d", &x); perm.push_back(x - 1); } return perm; } // An exponential algorithm // O(n * 2^n) histogram_t compute_histogram(const permutation_t permutation) { histogram_t ret; ret.resize(permutation.size() + 1, histogram_part_t{std::numeric_limits<uint64_t>::max(), 0}); std::vector<uint64_t> inversions; inversions.reserve(permutation.size()); inversions.push_back(0); // Pre-compute inversions for (unsigned int i = 1; i < permutation.size(); i++) { uint64_t mask = 0; for (unsigned int j = 0; j < i; j++) { if (permutation[j] > permutation[i]) { mask |= (uint64_t)1 << (uint64_t)j; } } inversions.push_back(mask); } // For each subset of the permutation, compute the best inversion count for (uint64_t subset = 0; subset < (uint64_t)1 << (uint64_t)permutation.size(); subset++) { uint64_t invs_for_set = 0; for (unsigned int i = 1; i < inversions.size(); i++) { if (subset & ((uint64_t)1 << (uint64_t)i)) { invs_for_set += __builtin_popcountll(subset & inversions[i]); } } const int idx = __builtin_popcountll(subset); ret[idx].inversions = std::min(ret[idx].inversions, invs_for_set); } // Now that we have the best counts, we can count the best subsets for (uint64_t subset = 0; subset < (uint64_t)1 << (uint64_t)permutation.size(); subset++) { uint64_t invs_for_set = 0; for (unsigned int i = 1; i < inversions.size(); i++) { if (subset & ((uint64_t)1 << (uint64_t)i)) { invs_for_set += __builtin_popcountll(subset & inversions[i]); } } const int idx = __builtin_popcountll(subset); if (ret[idx].inversions == invs_for_set) { ret[idx].count++; } } return ret; } void print_histogram(const histogram_t histogram) { for (unsigned int i = 1; i < histogram.size(); i++) { printf("%llu %llu\n", (unsigned long long int)histogram[i].inversions, (unsigned long long int)histogram[i].count); } } int main() { const auto perm = read_input(); const auto histogram = compute_histogram(std::move(perm)); print_histogram(std::move(histogram)); return 0; } |