Scribd Logo
Upload

Welcome to Scribd!

  • 38 views

    Ecnerwala 000000000069ae7c

    Uploaded by

    muhammad nur Alamsyah
    The document defines C++ structs tensor_view and tensor that represent multi-dimensional tensor views and tensors. Tensor_view stores the shape, strides, and data pointer of a tensor view. Tensor extends tensor_view by allocating storage for the tensor data. The main function reads in 2D tensors A and B along with row and column sums R and C, builds a map from B elements to their indices, and uses disjoint set unions to count matches between sums and tensor elements.

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd

    Ecnerwala 000000000069ae7c

    Uploaded by

    muhammad nur Alamsyah
    38 views4 pages
    The document defines C++ structs tensor_view and tensor that represent multi-dimensional tensor views and tensors. Tensor_view stores the shape, strides, and data pointer of a tensor view. Tensor extends tensor_view by allocating storage for the tensor data. The main function reads in 2D tensors A and B along with row and column sums R and C, builds a map from B elements to their indices, and uses disjoint set unions to count matches between sums and tensor elements.

    Original Title

    ecnerwala-000000000069ae7c

    Copyright

    © © All Rights Reserved

    Available Formats

    TXT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document defines C++ structs tensor_view and tensor that represent multi-dimensional tensor views and tensors. Tensor_view stores the shape, strides, and data pointer of a tensor view. Tensor extends tensor_view by allocating storage for the tensor data. The main function reads in 2D tensors A and B along with row and column sums R and C, builds a map from B elements to their indices, and uses disjoint set unions to count matches between sums and tensor elements.

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd
    Download as txt, pdf, or txt
    38 views4 pages

    Ecnerwala 000000000069ae7c

    Uploaded by

    muhammad nur Alamsyah
    The document defines C++ structs tensor_view and tensor that represent multi-dimensional tensor views and tensors. Tensor_view stores the shape, strides, and data pointer of a tensor view. Tensor extends tensor_view by allocating storage for the tensor data. The main function reads in 2D tensors A and B along with row and column sums R and C, builds a map from B elements to their indices, and uses disjoint set unions to count matches between sums and tensor elements.

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd
    Download as txt, pdf, or txt
    of 4

    #include<bits/stdc++.

    h>

    template <typename T, int NDIMS> struct tensor_view {


    static_assert(NDIMS >= 0, "NDIMS must be nonnegative");

    protected:
    std::array<int, NDIMS> shape;
    std::array<int, NDIMS> strides;
    T* data;

    tensor_view(std::array<int, NDIMS> shape_, std::array<int, NDIMS> strides_,


    T* data_) : shape(shape_), strides(strides_), data(data_) {}

    public:
    tensor_view() : shape{0}, strides{0}, data(nullptr) {}

    protected:
    int flatten_index(std::array<int, NDIMS> idx) const {
    int res = 0;
    for (int i = 0; i < NDIMS; i++) { res += idx[i] * strides[i]; }
    return res;
    }
    int flatten_index_checked(std::array<int, NDIMS> idx) const {
    int res = 0;
    for (int i = 0; i < NDIMS; i++) {
    assert(0 <= idx[i] && idx[i] < shape[i]);
    res += idx[i] * strides[i];
    }
    return res;
    }

    public:
    T& operator[] (std::array<int, NDIMS> idx) const {
    return data[flatten_index(idx)];
    }
    T& at(std::array<int, NDIMS> idx) const {
    return data[flatten_index_checked(idx)];
    }

    template <int D = NDIMS>


    typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type operator[]
    (int idx) const {
    std::array<int, NDIMS-1> nshape; std::copy(shape.begin()+1,
    shape.end(), nshape.begin());
    std::array<int, NDIMS-1> nstrides; std::copy(strides.begin()+1,
    strides.end(), nstrides.begin());
    T* ndata = data + (strides[0] * idx);
    return tensor_view<T, NDIMS-1>(nshape, nstrides, ndata);
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type at(int idx)
    const {
    assert(0 <= idx && idx < shape[0]);
    return operator[](idx);
    }

    template <int D = NDIMS>


    typename std::enable_if<(0 == D), T&>::type operator * () const {
    return *data;
    }

    template <typename U, int D> friend struct tensor_view;


    template <typename U, int D> friend struct tensor;
    };

    template <typename T, int NDIMS> struct tensor {


    static_assert(NDIMS >= 0, "NDIMS must be nonnegative");

    protected:
    std::array<int, NDIMS> shape;
    std::array<int, NDIMS> strides;
    int len;
    T* data;

    public:
    tensor() : shape{0}, strides{0}, len(0), data(nullptr) {}

    explicit tensor(std::array<int, NDIMS> shape_, const T& t = T()) {


    shape = shape_;
    strides[NDIMS-1] = 1;
    for (int i = NDIMS-1; i > 0; i--) {
    strides[i-1] = strides[i] * shape[i];
    }
    len = strides[0] * shape[0];
    data = new T[len];
    std::fill(data, data + len, t);
    }

    tensor(const tensor& o) : shape(o.shape), strides(o.strides), len(o.len),


    data(new T[len]) {
    for (int i = 0; i < len; i++) {
    data[i] = o.data[i];
    }
    }

    tensor& operator=(tensor&& o) noexcept {


    using std::swap;
    swap(shape, o.shape);
    swap(strides, o.strides);
    swap(len, o.len);
    swap(data, o.data);
    return *this;
    }
    tensor(tensor&& o) : tensor() {
    *this = std::move(o);
    }
    tensor& operator=(const tensor& o) {
    return *this = tensor(o);
    }
    ~tensor() { delete[] data; }

    using view_t = tensor_view<T, NDIMS>;


    view_t view() {
    return tensor_view<T, NDIMS>(shape, strides, data);
    }
    operator view_t() {
    return view();
    }
    using const_view_t = tensor_view<const T, NDIMS>;
    const_view_t view() const {
    return tensor_view<const T, NDIMS>(shape, strides, data);
    }
    operator const_view_t() const {
    return view();
    }

    T& operator[] (std::array<int, NDIMS> idx) { return view()[idx]; }


    T& at(std::array<int, NDIMS> idx) { return view().at(idx); }
    const T& operator[] (std::array<int, NDIMS> idx) const { return view()
    [idx]; }
    const T& at(std::array<int, NDIMS> idx) const { return view().at(idx); }

    template <int D = NDIMS>


    typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type operator[]
    (int idx) {
    return view()[idx];
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<T, NDIMS-1>>::type at(int idx) {
    return view().at(idx);
    }

    template <int D = NDIMS>


    typename std::enable_if<(0 < D), tensor_view<const T, NDIMS-1>>::type
    operator[] (int idx) const {
    return view()[idx];
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 < D), tensor_view<const T, NDIMS-1>>::type at(int
    idx) const {
    return view().at(idx);
    }

    template <int D = NDIMS>


    typename std::enable_if<(0 == D), T&>::type operator * () {
    return *view();
    }
    template <int D = NDIMS>
    typename std::enable_if<(0 == D), const T&>::type operator * () const {
    return *view();
    }
    };

    int main() {
    using namespace std;
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int T; cin >> T;


    for (int case_num = 1; case_num <= T; case_num ++) {

    int N; cin >> N;


    tensor<int, 2> A({N, N});
    for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
    cin >> A[{i,j}];
    }
    }
    tensor<int, 2> B({N, N});
    for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
    cin >> B[{i,j}];
    }
    }
    vector<int> R(N);
    for (auto& r : R) cin >> r;
    vector<int> C(N);
    for (auto& c : C) cin >> c;

    vector<vector<array<int, 2>>> vals(1001);


    for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
    vals[B[{i,j}]].push_back({i,j});
    }
    }

    const int V = 2 * N;
    vector<int> par(V, -1);
    auto get_par = [&](int a) -> int {
    while (par[a] >= 0) {
    if (par[par[a]] >= 0) par[a] = par[par[a]];
    a = par[a];
    }
    return a;
    };
    auto merge = [&](int a, int b) -> bool {
    a = get_par(a);
    b = get_par(b);
    if (a == b) return false;
    if (par[a] > par[b]) swap(a, b);
    par[a] += par[b];
    par[b] = a;
    return true;
    };

    int64_t ans = 0;
    for (int v = 1000; v >= 0; v--) {
    for (auto [i, j] : vals[v]) {
    if (!merge(i,N+j)) ans += v;
    }
    }

    cout << "Case #" << case_num << ": " << ans << '\n';
    }

    return 0;
    }

    You might also like