gt22

Untitled

Oct 10th, 2019
255
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  1. #include <vector>
  2. #include "optimization.h"
  3.  
  4. using namespace std;
  5.  
  6. int main() {
  7.     int m = readInt();
  8.     vector<pair<int, int>> arr, ans;
  9.     while(true) {
  10.         int a = readInt(), b = readInt();
  11.         if(a == 0 && b == 0) {
  12.             break;
  13.         }
  14.         if(b > 0) {
  15.             arr.emplace_back(a, b);
  16.         }
  17.     }
  18.     sort(arr.begin(), arr.end());
  19.     int curR = 0;
  20.     int maxR = -1;
  21.     for (int i = 0; i < arr.size(); i++) {
  22.         if(arr[i].first > curR) {
  23.             if(maxR == -1 || arr[maxR].second < arr[i].first) {
  24.                 writeWord("No solution\n");
  25.                 return 0;
  26.             } else {
  27.                 ans.push_back(arr[maxR]);
  28.                 curR = arr[maxR].second;
  29.                 maxR = -1;
  30.                 if(curR >= m) {
  31.                     break;
  32.                 }
  33.             }
  34.         }
  35.         if(maxR == -1 || arr[i].second > arr[maxR].second) {
  36.             maxR = i;
  37.         }
  38.     }
  39.     if(curR < m) {
  40.         if(maxR == -1 || arr[maxR].second < m) {
  41.             writeWord("No solution\n");
  42.             return 0;
  43.         }
  44.         ans.push_back(arr[maxR]);
  45.     }
  46.  
  47.     writeInt(ans.size(), '\n');
  48.     for(auto p : ans) {
  49.         writeInt(p.first, ' ');
  50.         writeInt(p.second, '\n');
  51.     }
  52.     return 0;
  53. }
Advertisement
Add Comment
Please, Sign In to add comment