Advertisement
Guest User

Untitled

a guest
Feb 26th, 2017
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.51 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <vector>
  6. #define ff first
  7. #define ss second
  8. using namespace std;
  9.  
  10. bool condLeft(int x, vector<pair<int,char>>m)
  11. {
  12. int n = m.size();
  13. for (int i = 0; i < n; i++)
  14. {
  15. if (m[i].ss == 'R' && x < 1) return false;
  16. else if (m[i].ss == 'Y' && x + 1 > m[i].ff) return false;
  17. else if (m[i].ss == 'G' && 2 * x + 1 > m[i].ff) return false;
  18. }
  19. return true;
  20. }
  21. bool condRight(int x, vector<pair<int, char>>m)
  22. {
  23. int n = m.size();
  24. for (int i = 0; i < n; i++)
  25. {
  26. if (m[i].ss == 'R' && x < m[i].ss) return false;
  27. else if (m[i].ss == 'Y' && 2*x < m[i].ff) return false;
  28. else if (m[i].ss == 'G' && 3 * x < m[i].ff) return false;
  29. else if (m[i].ss == 'Z' && 3 * x + 1 > m[i].ff) return false;
  30. }
  31. return true;
  32. }
  33.  
  34. int binSearchLeft(vector<pair<int, char>>m)
  35. {
  36. int l = 0, r = 2 * 1e9 + 1;
  37. while (r-l!=1)
  38. {
  39. int mid = (l + r) / 2;
  40. if (condLeft(mid,m)) l = mid;
  41. else r = mid;
  42. }
  43. return r;
  44. }
  45. int binSearchRight(vector<pair<int, char>>m)
  46. {
  47. int l = 0, r = 2 * 1e9 + 1;
  48. while (r - l != 1)
  49. {
  50. int mid = (l + r) / 2;
  51. if (condRight(mid, m)) l = mid;
  52. else r = mid;
  53. }
  54. return r;
  55. }
  56. int main()
  57. {
  58. int n,a;
  59. cin >> n;
  60. char r;
  61. vector<pair<int, char>> m;
  62. for (int i = 0;i<n;i++)
  63. {
  64. cin >> a >> r;
  65. m.push_back(make_pair(a, r));
  66. }
  67. int left = binSearchLeft(m);
  68. int right = binSearchRight(m);
  69. if (left > right) cout << "-1";
  70. else cout << left << ' ' << right;
  71. return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement