Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <map>
- #include <vector>
- #include <algorithm>
- using namespace std;
- class slon
- {
- public:
- int iq, waga, numer;
- };
- bool c1(slon a,slon b)
- {
- if(a.iq==b.iq)
- return a.waga > b.waga;
- return a.iq > b.iq;
- }
- bool c2(slon a,slon b)
- {
- if(a.waga==b.waga)
- return a.iq < b.iq;
- return a.waga < b.waga;
- }
- int LCS(vector <slon>a, vector<slon> b, vector<int> &tab)
- {
- slon te;
- a.insert(a.begin(),te);
- b.insert(b.begin(),te);
- int as = a.size();
- int bs = b.size();
- //printf("%d %d\n",as,bs);
- int c[as][bs];
- int ile=0;
- for(int i=0;i<as;i++)
- {
- c[i][0]=0;
- // printf("%d ",b[i].numer);
- }
- for(int i=0;i<bs;i++)
- c[0][i]=0;
- for(int i=1;i<as;i++)
- {
- for(int j=1; j<bs; j++)
- {
- // printf("%d ", c[i][j]);
- if(a[i].numer == b[j].numer)
- {
- c[i][j]=c[i-1][j-1]+1;
- // if(ile<c[i][j]+1)
- //{
- //tab.push_back(a[i].numer);
- //printf("aa: %d\n",a[i].numer);
- //ile++;
- //printf("sss: %d %d %d\n",i+1,j+1,c[i+1][j+1]);
- //}
- }
- else
- {
- c[i][j] = max(c[i][j-1],c[i-1][j]);
- }
- }
- // printf("\n");
- }
- int x = as-1;
- int y = bs-1;
- while (x && y)
- {
- if(a[x].numer == b[y].numer)
- {
- tab.push_back(a[x].numer);
- x--;
- y--;
- }
- else
- {
- if(c[x-1][y] >= c[x][y-1])
- x--;
- else
- y--;
- }
- }
- return c[as-1][bs-1];
- }
- int main()
- {
- slon temp;
- vector <slon> kk,kk2;
- vector <int> ll;
- int w,iq,i;
- i=0;
- while(scanf("%d%d",&w,&iq)!=EOF)
- {
- i++;
- temp.numer = i;
- temp.waga = w;
- temp.iq = iq;
- kk.push_back(temp);
- }
- kk2.insert(kk2.begin(),kk.begin(),kk.end());
- sort(kk.begin(),kk.end(),c1);
- sort(kk2.begin(),kk2.end(),c2);
- printf("%d\n",LCS(kk,kk2,ll));
- reverse(ll.begin(),ll.end());
- for(int i=0;i<ll.size();i++)
- printf("%d\n",ll[i]);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement