Submission #945816

#TimeUsernameProblemLanguageResultExecution timeMemory
945816itslqRoad Construction (JOI21_road_construction)C++17
11 / 100
10026 ms1054600 KiB
#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; l = ++m; } else { r = --m; } } vector<int> dist; dist.clear(); 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'; for (int i = dist.size(); i < K; i++) cout << ans + 1 << '\n'; } }

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:70:61: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   70 |         for (int i = dist.size(); i < K; i++) cout << ans + 1 << '\n';
      |                                                             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...