QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#120623#1154. WombatsQwerty1232#Compile Error//C++173.9kb2023-07-07 01:35:232024-05-26 02:57:05

Judging History

你现在查看的是最新测评结果

  • [2024-05-26 02:57:05]
  • 评测
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-07 01:35:23]
  • 提交

answer

#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include "wombats.h"

#include <bits/stdc++.h>

constexpr int inf = 1e9 + 1;
int n, m;

struct Cum {
    std::vector<int> L;
    std::vector<std::vector<int>> data;

    std::vector<std::vector<int>> v, h;
    int len;

    Cum() {
        len = 0;
    }
    Cum(std::vector<int> v, std::vector<int> h) {
        assert(v.size() == m);
        assert(h.size() == m - 1);
        len = 1;
        L = v;
        this->v.push_back(v);
        this->h.push_back(h);
        return;
        std::vector<int> ph(m);
        std::partial_sum(h.begin(), h.end(), ph.begin() + 1);
        data.assign(m, std::vector<int>(m));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                data[i][j] = abs(ph[i] - ph[j]);
            }
        }
    }
};

Cum fuck(Cum a) {
    if (a.len == -1) {
        return a;
    }
    int l = a.len;
    Cum res;
    res.len = -1;
    res.data.resize(m);
    res.L = a.L;
    for (int i = 0; i < m; i++) {
        std::vector<int> dp(m, inf);
        dp[i] = 0;
        auto shit = [&](auto& h) {
            for (int j = 1; j < m; j++) {
                dp[j] = std::min(dp[j], dp[j - 1] + h[j - 1]);
            }
            for (int j = m - 2; j >= 0; j--) {
                dp[j] = std::min(dp[j], dp[j + 1] + h[j]);
            }
        };
        shit(a.h[0]);
        for (int j = 1; j < l; j++) {
            for (int t = 0; t < m; t++) {
                dp[t] += a.v[j][t];
            }
            shit(a.h[j]);
        }
        res.data[i] = dp;
    }
    return res;
}

Cum merge(Cum a, Cum b) {
    if (!a.len || !b.len) {
        return a.len ? a : b;
    }
    // a = fuck(a);
    // b = fuck(b);
    if (a.len == -1 || b.len == -1) {
        if (a.len != -1) {
            a = fuck(a);
        }
        if (b.len != -1) {
            b = fuck(b);
        }
    } else {
        a.len += b.len;
        a.v.insert(a.v.end(), b.v.begin(), b.v.end());
        a.h.insert(a.h.end(), b.h.begin(), b.h.end());
        if (a.len > 30) {
            a = fuck(a);
        }
        return a;
    }
    Cum res;
    res.len = -1;
    res.L = a.L;
    res.data.assign(m, std::vector<int>(m, inf));
    const int const_m = m;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            int val = a.data[i][j] + b.L[j];
#pragma GCC ivdep
            for (int t = 0; t < const_m; t++) {
                res.data[i][t] = std::min(res.data[i][t], val + b.data[j][t]);
            }
        }
    }
    return res;
}

std::vector<std::vector<int>> h, v;

int size;
std::vector<Cum> data;

void build() {
    for (size = 1; size < n; size *= 2)
        ;
    data.resize(2 * size);
    for (int i = 0; i < n; i++) {
        data[size + i] = Cum(v[i], h[i]);
    }
    for (int i = size - 1; i > 0; i--) {
        data[i] = merge(data[2 * i], data[2 * i + 1]);
    }
}

void update(int i) {
    data[i + size] = Cum(v[i], h[i]);
    i += size;
    for (i >>= 1; i > 0; i >>= 1) {
        data[i] = merge(data[2 * i], data[2 * i + 1]);
    }
}

void init(int r, int c, int H[5000][200], int V[5000][200]) {
    n = r;
    m = c;
    h.assign(n, std::vector<int>(m - 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m - 1; j++) {
            h[i][j] = H[i][j];
        }
    }
    v.assign(n, std::vector<int>(m));
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m; j++) {
            v[i + 1][j] = V[i][j];
        }
    }
    build();
}

void changeH(int p, int q, int w) {
    h[p][q] = w;
    update(p);
}

void changeV(int p, int q, int w) {
    v[p + 1][q] = w;
    update(p + 1);
}

int escape(int v1, int v2) {
    if (data[1].len != -1) {
        data[1] = fuck(data[1]);
    }

    int res = data[1].data[v1][v2];
    return res;
    // return 42;
}

详细

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from answer.code:5:
/usr/include/c++/13/bits/allocator.h: In destructor ‘std::_Vector_base<int, std::allocator<int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~