Guest User

Untitled

a guest
Nov 13th, 2015
156
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