Advertisement
Guest User

Untitled

a guest
Sep 17th, 2015
251
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. typedef std::pair<std::pair<int, int> , int> para;
  4.  
  5. bool comp(para p1, para p2)
  6. {
  7.     if(p1.first.first != p2.first.first)
  8.         return p1.first.first < p2.first.first;
  9.     else
  10.         return p1.first.second < p2.first.second;
  11. }
  12.  
  13. int main()
  14. {
  15.     std::vector<para> tab;
  16.  
  17.     std::pair<int, int> w;
  18.  
  19.     for(int i = 1; scanf("%d %d", &w.first, &w.second) != EOF; ++i)
  20.     {
  21.         tab.push_back(std::make_pair(w, i));
  22.     }
  23.  
  24.     std::sort(tab.begin(), tab.end(), comp);
  25.  
  26.     int *poprzednik = new int[tab.size()+1];
  27.     int *d = new int[tab.size()+1];
  28.  
  29.     d[0] = 1;
  30.     poprzednik[0] = -1;
  31.  
  32.     for(int i = 1; i < tab.size(); ++i)
  33.     {
  34.         int act = tab[i].first.second;
  35.         d[i] = 1;
  36.         poprzednik[i] = -1;
  37.  
  38.         for(int j = 0; j < i; ++j)
  39.         {
  40.             if(act < tab[j].first.second)
  41.             {
  42.                 if(d[i] <= d[j])
  43.                 {
  44.                     d[i] = d[j]+1;
  45.                     poprzednik[i] = j;
  46.                 }
  47.             }
  48.         }
  49.     }
  50.  
  51.     int MAX = 0;
  52.     int poprzmax;
  53.  
  54.     for(int i = 0; i < tab.size(); ++i)
  55.     {
  56.         if(d[i] > MAX)
  57.         {
  58.             MAX = d[i];
  59.             poprzmax = i;
  60.         }
  61.     }
  62.  
  63.     printf("%d\n", MAX);
  64.  
  65.     while(poprzmax != -1)
  66.     {
  67.         printf("%d\n", tab[poprzmax].second);
  68.         poprzmax = poprzednik[poprzmax];
  69.     }
  70. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement