提出 #67009439

---

ソースコード 拡げる

#include <bits/stdc++.h>

// what the fuck
template<typename T, int N>
struct NDVector { using type = std::vector<typename NDVector<T, N - 1>::type>; };
template<typename T>
struct NDVector<T, 1> { using type = std::vector<T>; };

// A tensor is essentially a vector of tensors. (or multidimensional array)
template<typename T, int N>
using Tensor = typename NDVector<T, N>::type;

/**
 * Create a multidimensional vector with the given dimension sizes.
 *
 * In particular, create_vector(N) = create_tensor(N), create_matrix(N, M) = create_tensor(N, M).
 * If you have some weird multidimensional DP, you can create the DP table by doing:
 *      dp = create_tensor(5, 5, 5, 5, 5);
 *
 * Be careful, for a large number of dimensions, this uses a lot of memory and is very cache unfriendly.
 */
template<typename T>
std::vector<T> create_tensor(int N) {
    return std::vector<T>(N);
}
template <typename T, typename... ArgTypes>
Tensor<T, sizeof...(ArgTypes) + 1> create_tensor(int N, ArgTypes... args) {
    auto under = create_tensor<T>(args...);
    return std::vector(N, under);
}

/**
 * Create a matrix of the given dimensions.
 */
template<typename T>
Tensor<T, 2> create_matrix(int N, int M) {
    return create_tensor<T>(N, M);
}

/**
 * Frequently used definitions, like Vector, Matrices, pairs of ints, pairs, triples, etc.
 */
template<typename T>
using Vector = Tensor<T, 1>; // I could use std::vector<T>, but this is just too cool.
template<typename T>
using Matrix = Tensor<T, 2>;

template<typename T1, typename T2>
using Pair = std::pair<T1, T2>;
using PairII = Pair<int, int>;
using PairLL = Pair<long long, long long>;

template<typename T1, typename T2, typename T3>
using Triple = std::tuple<T1, T2, T3>;

/**
 * Read a vector from input. Set start to 1 if you want it to be 1-indexed.
 */
template<typename T>
Vector<T> read_vector(int N, int start = 0) {
    Vector<T> v(start + N);
    for (int i = start; i < (int)v.size(); i++) {
        std::cin >> v[i];
    }
    return v;
}

/**
 * Read a matrix from input. Set start_l to make lines 1-indexed. Same thing for start_c.
 */
template<typename T>
Matrix<T> read_matrix(int N, int M, int start_l = 0, int start_c = 0) {
    Matrix<T> matr = create_matrix<T>(N + start_l, M + start_c);

    for (int l = start_l; l < N + start_l; l++)
        for (int c = start_c; c < M + start_c; c++)
            std::cin >> matr[l][c];

    return matr;
}

/**
 * Print a tensor to the output stream. Prints all indices between i and j, and the elements 
 * are separated by the given separator.
 *
 * To generalize, for each dimension, you give the bounds that you want to print and the separator
 * between each order. To print a matrix, you would do:
 *
 *      print_tensor(matr, std::cout, 0, N - 1, "\n", 0, M - 1, " ");
 */
template<typename T>
void print_tensor(Tensor<T, 1>& tens, std::ostream&fout, int i, int j, const char* sep) {
    for (int t = std::max(i, 0); t <= j && t < (int)tens.size(); t++) {
        fout << tens[t];
        if (t + 1 <= j)
            fout << sep;
    }
}

template<typename T, typename... Sizes>
void print_tensor(
        Tensor<T, sizeof...(Sizes) / 3 + 1>& tens,
        std::ostream& fout, 
        int i, int j, const char* sep, Sizes... sizes) {
    for (int t = std::max(i, 0); t <= j && t < (int)tens.size(); t++) {
        print_tensor<T>(tens[t], fout, sizes...);
        if (t + 1 <= j)
            fout << sep;
    }
}

/**
 * Print a vector to the given output stream with given bounds and separator.
 */
template<typename T>
void print_vector(std::vector<T>& v, std::ostream& fout, int i = 0, int j = (1 << 30), const char* sep = " ") {
    print_tensor<T>(v, fout, i, j, sep);
}

/**
 * Read a vector of pairs. Set start to 1 if you want this to be 1-indexed.
 */
template<typename T1, typename T2>
Vector<Pair<T1, T2>> read_pairvec(int N, int start = 0) {
    Vector<Pair<T1, T2>> input = Vector<Pair<T1, T2>>(start + N);
    for (int i = start; i < start + N; i++)
        std::cin >> input[i].first >> input[i].second;
    return input;
}

/**
 * Read a vector of triples. Set start to 1 if you want this to be 1-indexed.
 *
 * If you need higher order tuples, like quadruples, you're better off using a matrix instead.
 */
template<typename T1, typename T2, typename T3>
Vector<Triple<T1, T2, T3>> read_triplevec(int N, int start = 0) {
    Vector<Triple<T1, T2, T3>> input = Vector<Triple<T1, T2, T3>>(start + N);
    for (int i = start; i < N + start; i++) {
        T1 a;
        T2 b;
        T3 c;
        std::cin >> a >> b >> c;
        input[i] = {a, b, c};
    }
    return input;
}

/**
 * Removes duplicates from vector. Assumes it is sorted.
 */
template<typename T>
void deduplicate(Vector<T>& v) {
    v.resize(std::unique(v.begin(), v.end()) - v.begin());    
}

/**
 * Solve a testcase of the problem. You will code your solution here instead of main.
 */
void solve_test();

/**
 * Call this function if you have a problem with multiple testcases.
 */
void multitest_problem() {
    int T;
    std::cin >> T;

    while (T--) solve_test();
}

int main() {
    std::cin.tie(NULL);
    std::iostream::sync_with_stdio(false);

    // Choose one of the following functions, depending on the problem type.
    // solve_test();
    multitest_problem();

    return 0;
}


void solve_test() {
    int N;
    int64_t M;
    std::cin >> N >> M;

    auto A = read_vector<int64_t>(N);
    auto B = read_vector<int64_t>(N);

    std::sort(A.rbegin(), A.rend());
    std::sort(B.begin(), B.end());

    for (int c = 1; c <= 4; c++) {
        for (int i = 0; i < N; i++)
            B.push_back(B[i] + c * M);
    }

    auto check = [&](int mid) {
        Vector<PairLL> ranges, ranges_norm;
        int64_t last = 0;
        for (int i = 0; i < N; i++) {
            int64_t l = -A[i] + M;
            int64_t r = mid - A[i] + M;
            ranges.push_back({l, r});
        }

        for (int i = 0; i < N; i++)
            ranges.push_back({ranges[i].first + M, ranges[i].second + M});

        int pl = -1, pr = -1;
        for (auto [l, r] : ranges) {
            while (pr + 1 < B.size() && B[pr + 1] <= r) pr++;
            while (pl + 1 < B.size() && B[pl + 1] < l) pl++;

            ranges_norm.push_back({pl + 1, pr});
        }

        for (int i = 0; i < ranges.size(); i++) {
            auto [l, r] = ranges_norm[i];
            if (l > r) return false;
        }

        for (int i = 0; i + 1 < ranges.size(); i++)
            if (N > 1 && ranges_norm[i].second + 1 < ranges_norm[i + 1].first) {
                return false;
            }

        int lazy = 0;
        Vector<int64_t> value;
        std::deque<int> dq;

        pl = 0;
        for (int i = 0; i < ranges_norm.size(); i++) {
            auto [l, r] = ranges_norm[i];

            value.push_back(l - lazy);
            lazy++;

            while (!dq.empty() && value[dq.back()] < value[i])
                dq.pop_back();
            dq.push_back(i);

            while (pl < i && ranges_norm[pl].first + M < r) {
                if (!dq.empty() && dq.front() == pl)
                    dq.pop_front();
                pl++;
            }

            if (dq.empty()) return false;
            if (value[dq.front()] + lazy > r + 1) return false;
        }

        return true;
    };

    int l = -1, r = M;
    while (r - l > 1) {
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid;
    }

    std::cout << r << "\n";
}

提出情報

コンパイルエラー

Main.cpp: In lambda function:
Main.cpp:214:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long int, std::allocator<long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  214 |             while (pr + 1 < B.size() && B[pr + 1] <= r) pr++;
      |                    ~~~~~~~^~~~~~~~~~
Main.cpp:215:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<long int, std::allocator<long int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  215 |             while (pl + 1 < B.size() && B[pl + 1] < l) pl++;
      |                    ~~~~~~~^~~~~~~~~~
Main.cpp:220:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  220 |         for (int i = 0; i < ranges.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~
Main.cpp:225:31: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  225 |         for (int i = 0; i + 1 < ranges.size(); i++)
      |                         ~~~~~~^~~~~~~~~~~~~~~
Main.cpp:235:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<long long int, long long int>, std::allocator<std::pair<long long int, long long int> > >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  235 |         for (int i = 0; i < ranges_norm.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:202:17: warning: unused variable ‘last’ [-Wunused-variable]
  202 |         int64_t last = 0;
      |                 ^~~~

ジャッジ結果