Guest User

Untitled

a guest
Nov 13th, 2015
217
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <algorithm>
  3. #include <iostream>
  4.  
  5. using namespace std;
  6.  
  7.  
  8. struct v2
  9. {
  10. int a;
  11. int b;
  12. };
  13.  
  14. bool sort1(v2 a, v2 b){
  15. if(a.a == b.a)
  16. return a.b < b.b;
  17. return a.a < b.a;
  18. }
  19. bool sort2(v2 a, v2 b){
  20. if(a.b == b.b)
  21. return a.a < b.a;
  22. return a.b < b.b;
  23. }
  24.  
  25. int main()
  26. {
  27. int n, x, y=0;
  28. cin >> n;
  29. cin >> x;
  30. cin >> y;
  31. vector<v2> cs; // list of competition starts and end times
  32. for(int i =0;i<n;i++)
  33. {
  34. v2 a;
  35. cin >> a.a;
  36. cin >> a.b;
  37. cs.push_back(a);
  38. }
  39.  
  40. vector<int> is; //in wormholes
  41. vector<int> es; //out wormholes
  42. for(int i =0;i<x;i++)
  43. {
  44. int ax = 0;
  45. cin >> ax;
  46. is.push_back(ax);
  47. }
  48. for(int i =0;i<y;i++)
  49. {
  50. int ax = 0;
  51. cin >> ax;
  52. es.push_back(ax);
  53. }
  54.  
  55. //sort in ascending order
  56. sort(is.begin(), is.end());
  57. //sort first by end time, then matched ones are sorted by start time in ascending
  58. sort(cs.begin(), cs.end(), sort2);
  59. sort(es.begin(), es.end());
  60.  
  61. //compare every single to find the best way giving O(n^3) but because the arrays are
  62. //already sorted we just need to check the first element that fits the condition
  63. //after this the index is saved so that again in next loop we don't check from the beginning
  64. int out = 1000000;
  65. int* dp = new int[x]();
  66. int p1 =0, p2=0;
  67. for(int i = 0;i<x;i++)
  68. {
  69. for(int ab = p1; ab<n;ab++)
  70. {
  71. if(cs[ab].a >= is[i])
  72. {
  73. // cout << "B" << is[i] << "\n";
  74.  
  75. bool tset = false;
  76. for(int ac = p2;ac<y;ac++)
  77. {
  78. // cout << "C" << es[ac] << "\n";
  79. if(cs[ab].b <= es[ac])
  80. {
  81.  
  82. //cout << "A: " << cs[ab].a << " " << is[i] << " " << es[i] << "\n";
  83. int time= es[ac] - is[i] + 1;
  84. if(time < out)
  85. out = time;
  86. tset =true;
  87. break;
  88. }
  89.  
  90. p2 = ac;
  91. }
  92. if(tset)
  93. break;
  94. }
  95.  
  96. p1 = ab;
  97. //p1++;
  98. }
  99. }
  100. cout << out;
  101.  
  102. }
RAW Paste Data