Submission #945773

#	Time	Username	Problem	Language	Result	Execution time	Memory
945773		itslq	Road Construction (JOI21_road_construction)	C++17	5 / 100	384 ms	7088 KiB

road_construction

#include <bits/stdc++.h>
using namespace std;

#define int long long

int N;
vector<int> x;

int check(int d) {
    int S = 0;
    for (int i = 0; i < N; i++) {
        S += upper_bound(x.begin(), x.end(), x[i] + d) - x.begin() - i - 1;
    }
    return S;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int K;
    cin >> N >> K;

    if (N <= 1000) {
        vector<int> dist;
        vector<pair<int, int>> pos(N);
        for (int i = 0; i < N; i++) cin >> pos[i].first >> pos[i].second;

        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                dist.push_back(abs(pos[i].first - pos[j].first) + abs(pos[i].second - pos[j].second));
            }
        }

        sort(dist.begin(), dist.end());
        for (int i = 0; i < K; i++) cout << dist[i] << '\n';

    } else {
        int j;
        x.resize(N);
        for (int i = 0; i < N; i++) cin >> x[i] >> j;
        sort(x.begin(), x.end());

        int l = 0, r = 2e9, m, ans;

        while (l <= r) {
            m = (l + r) >> 1;
            if (check(m) >= K) {
                ans = m;
                r = --m;
            } else {
                l = ++m;
            }
        }

        vector<int> dist;

        for (int i = 0; i < N; i++) {
            j = i + 1;
            while (j < N && x[j] - x[i] <= ans) {
                dist.push_back(x[j] - x[i]);
                j++;
            }
        }

        sort(dist.begin(), dist.end());

        for (int x: dist) cout << x << '\n';
    }
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:60:26: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   60 |             while (j < N && x[j] - x[i] <= ans) {
      |                    ~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35