Advertisement
lucacodorean

Untitled

Jan 18th, 2020
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.29 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <algorithm>
  4. #include <queue>
  5. using namespace std;
  6.  
  7. ifstream fin("medici.in");
  8. ofstream fout("medici.out");
  9.  
  10. struct coordonate
  11. {
  12.     int x,y,poz;
  13.     bool ok=false;
  14. } a[1001];
  15.  
  16. int plan[1001];
  17. queue<pair<int,int> >q;
  18.  
  19. bool intersectie (pair <int,int>a, pair<int,int>b)
  20. {
  21.     if(a.second>=b.first && a.first<=b.second)
  22.     {
  23.         return false;
  24.     }
  25.     return true;
  26. }
  27.  
  28. bool corect(coordonate a, coordonate b)
  29. {
  30.    return a.y<b.y;
  31. }
  32.  
  33. int main()
  34. {
  35.     int n,cate=0;
  36.     fin>>n;
  37.     for(int i=1; i<=n; i++)
  38.     {
  39.         fin>>a[i].x;
  40.         a[i].poz=i;
  41.     }
  42.     for(int i=1; i<=n; i++)
  43.     {
  44.         fin>>a[i].y;
  45.     }
  46.     fin.close();
  47.     sort(a+1,a+n+1, corect);
  48.  
  49.     for(int i=1; i<=n; i++)
  50.     {
  51.         while(!q.empty() && intersectie(q.front(), {a[i].x, a[i].y})==false)
  52.         {
  53.                 a[i].x=min(q.front().first, a[i].x);
  54.                 a[i].y=max(q.front().second,a[i].y);
  55.                 a[i].ok=true;
  56.                 cate+=1;
  57.                 q.pop();
  58.         }
  59.         q.push({a[i].x,a[i].y});
  60.     }
  61.  
  62.     fout<<cate<<endl;
  63.     for(int i=1; i<=n; i++)
  64.     {
  65.         if(a[i].ok==true)
  66.         {
  67.             fout<<a[i].poz<<" ";
  68.         }
  69.     }
  70.     fout.close();
  71.     return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement