Advertisement
Guest User

Untitled

a guest
Jun 22nd, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.93 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <map>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. class slon
  10. {
  11. public:
  12. int iq, waga, numer;
  13. };
  14.  
  15. bool c1(slon a,slon b)
  16. {
  17. if(a.iq==b.iq)
  18. return a.waga > b.waga;
  19. return a.iq > b.iq;
  20.  
  21. }
  22.  
  23. bool c2(slon a,slon b)
  24. {
  25. if(a.waga==b.waga)
  26. return a.iq < b.iq;
  27. return a.waga < b.waga;
  28.  
  29. }
  30.  
  31. int LCS(vector <slon>a, vector<slon> b, vector<int> &tab)
  32. {
  33. slon te;
  34.  
  35. a.insert(a.begin(),te);
  36. b.insert(b.begin(),te);
  37. int as = a.size();
  38. int bs = b.size();
  39. //printf("%d %d\n",as,bs);
  40. int c[as][bs];
  41. int ile=0;
  42. for(int i=0;i<as;i++)
  43. {
  44. c[i][0]=0;
  45. // printf("%d ",b[i].numer);
  46. }
  47. for(int i=0;i<bs;i++)
  48. c[0][i]=0;
  49.  
  50. for(int i=1;i<as;i++)
  51. {
  52. for(int j=1; j<bs; j++)
  53. {
  54. // printf("%d ", c[i][j]);
  55. if(a[i].numer == b[j].numer)
  56. {
  57.  
  58. c[i][j]=c[i-1][j-1]+1;
  59.  
  60. // if(ile<c[i][j]+1)
  61. //{
  62. //tab.push_back(a[i].numer);
  63. //printf("aa: %d\n",a[i].numer);
  64. //ile++;
  65. //printf("sss: %d %d %d\n",i+1,j+1,c[i+1][j+1]);
  66. //}
  67. }
  68. else
  69. {
  70. c[i][j] = max(c[i][j-1],c[i-1][j]);
  71.  
  72.  
  73.  
  74. }
  75.  
  76. }
  77. // printf("\n");
  78. }
  79.  
  80. int x = as-1;
  81. int y = bs-1;
  82.  
  83. while (x && y)
  84. {
  85. if(a[x].numer == b[y].numer)
  86. {
  87. tab.push_back(a[x].numer);
  88. x--;
  89. y--;
  90. }
  91. else
  92. {
  93. if(c[x-1][y] >= c[x][y-1])
  94. x--;
  95. else
  96. y--;
  97. }
  98. }
  99.  
  100.  
  101. return c[as-1][bs-1];
  102. }
  103.  
  104.  
  105. int main()
  106. {
  107. slon temp;
  108. vector <slon> kk,kk2;
  109. vector <int> ll;
  110.  
  111. int w,iq,i;
  112. i=0;
  113. while(scanf("%d%d",&w,&iq)!=EOF)
  114. {
  115.  
  116. i++;
  117. temp.numer = i;
  118. temp.waga = w;
  119. temp.iq = iq;
  120.  
  121. kk.push_back(temp);
  122. }
  123. kk2.insert(kk2.begin(),kk.begin(),kk.end());
  124. sort(kk.begin(),kk.end(),c1);
  125. sort(kk2.begin(),kk2.end(),c2);
  126.  
  127. printf("%d\n",LCS(kk,kk2,ll));
  128. reverse(ll.begin(),ll.end());
  129. for(int i=0;i<ll.size();i++)
  130. printf("%d\n",ll[i]);
  131.  
  132.  
  133.  
  134. return 0;
  135. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement