F - spices (linear basis)

F - Spices( Linear base )

The conclusion is that $[1,2^n-1]$ At most $n$ Number can be expressed $[1,2^n-1]$ , The principle is a linear basis .

Because of the demand $value$ Minimum , So sort by value , Then simulate the linear basis .

Time complexity ：$O(n{2}^n)$

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::vector<std::pair<int, int>> a((1 << n) - 1);
    for (int i = 0; i < (1 << n) - 1; i++) {
    
        int x;
        std::cin >> x;
        a[i] = {
    x, i + 1};
    }
    
    std::sort(a.begin(), a.end());
    
    i64 ans = 0;
    
    std::vector<int> t(n);
    for (auto [v, x] : a) {
    
        for (int i = 0; i < n; i++) {
    
            if (x >> i & 1) {
    
                if (t[i] == 0) {
    
                    ans += v;
                    t[i] = x;
                    break;
                }
                x ^= t[i];
            }
        }
    }
    
    std::cout << ans << "\n";
    
    return 0;
}