• API
• FAQ
• Tools
• Archive
SHARE
TWEET # NailingPlanks a guest Mar 29th, 2020 99 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <algorithm>
2. #include <limits>
3. #include <set>
4.
5. bool checkAllNailed(const vector<pair<int, int>>& planks, const vector<int> &C, int j) {
6.     vector<int> nails;
7.     for (int i = 0; i <= j; i++) {
8.         nails.push_back(C[i]);
9.     }
10.     sort(nails.begin(), nails.end());
11.
12.     int p = 0;
13.     for (const int nail : nails) {
14.         while (p < planks.size() && planks[p].first <= nail) {
15.             if (planks[p].second < nail) {
16.                 return false;
17.             }
18.             p++;
19.         }
20.     }
21.     return (p == planks.size());
22. }
23.
24. int solution(vector<int> &A, vector<int> &B, vector<int> &C) {
25.     vector<pair<int, int>> planks;
26.     for (int i = 0; i < A.size(); i++) {
27.         planks.push_back(make_pair(A[i], B[i]));
28.     }
29.     sort(planks.begin(), planks.end());
30.
31.     int s = 0;
32.     int e = C.size() - 1;
33.     while (s != e) {
34.         int m = (s + e) / 2;
35.
36.         bool solves = checkAllNailed(planks, C, m);
37.         if (solves) {
38.             e = m;
39.         } else {
40.             s = m + 1;
41.         }
42.     }
43.
44.     if (checkAllNailed(planks, C, s)) {
45.         return s + 1;
46.     }
47.     return -1;
48. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.
Top