Submission #67006437

---

Source Code Expand

#include <bits/stdc++.h>

std::vector<long long> duplicate(const std::vector<long long> &a, long long m, int l, int r) {
    std::vector<long long> ans;
    for(int i = l; i <= r; i++) {
        // std::cout << "with i " << i << std::endl;
        for(auto x : a) {
            ans.push_back(x + i * m);
        }
    }
    return ans;
}

bool check(int x, std::vector<long long> &a, std::vector<long long> &b, int n, int m) {
    // std::cout << "checking for " << x << '\n';
    std::vector<int> l(2 * n), r(2 * n);
    for(int i = 0, j = 0, k = 0; i < 2 * n; i++) {
        while(j < 3 * n && a[j] < b[i]) j++;
        while(k < 3 * n && a[k] <= b[i] + x) k++;
        l[i] = j, r[i] = k;
        // std::cout << "range for " << i << " is " << l[i] << ", " << r[i] << '\n';
        if(r[i] - l[i] == 0) return false;
    }
    int worst = r[0] - l[0] - 1;
    for(int i = 1; i < 2 * n; i++) {
        worst = std::min(worst + r[i] - r[i-1], r[i] - l[i]) - 1;
        // std::cout << "at " << i << " got " << worst << std::endl;
        if(worst < 0) return false;
    }
    return true;
}

int main() {
    std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while(t--) {
        int n, m;
        std::cin >> n >> m;
        std::vector<long long> a(n), b(n);
        for(int i = 0; i < n; i++) std::cin >> a[i];
        for(int i = 0; i < n; i++) std::cin >> b[i];
        for(int i = 0; i < n; i++) b[i] = (m - b[i]) % m;
        std::sort(a.begin(), a.end()), std::sort(b.begin(), b.end());
        a = duplicate(a, m, 0, 2), b = duplicate(b, m, 0, 1);
        int l = 0, r = m-1;
        while(l != r) {
            int mid = (l + r) / 2;
            if(check(mid, a, b, n, m)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        std::cout << l << '\n';
    }
}

Submission Info

Compile Error

Main.cpp: In function ‘bool check(int, std::vector<long long int>&, std::vector<long long int>&, int, int)’:
Main.cpp:14:84: warning: unused parameter ‘m’ [-Wunused-parameter]
   14 | bool check(int x, std::vector<long long> &a, std::vector<long long> &b, int n, int m) {
      |                                                                                ~~~~^

Judge Result