uva 10131 - Is Bigger Smarter?

/*

Problem link
- This problem is a good example of both LIS and LCS. I solved this problem
using the LCS DP (Longest Common sub-Sequence).
** Algorithm:
- The algorithm for the LCS is simple. 
- First we sort the list of the cows in increasing 
order of weight, save their corresponding ID in array l1.
- Second, sort the list of the cows in decreasing 
order of smart, save their corresponding ID in array l2.
- Find the LCS of l1 and l2.
** Example for the sample input, we have:
 l1: 3 4 5 9 8 6 2 1 7 
 l2: 4 5 2 3 6 9 7 1 8 
The LCS is: 4 5 9 7 or 4 5 2 7 is the answer.
** Note: Since the problem required the STRICTLY increasing of weight and 
decreasing of smart, the LCS cannot afford this. We have to do a double-check,
that is, throughout the trace back procedure, we check the condition before
we add them to the answer.
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
using namespace std;
const int maxn = 1010;
//-----------------------------
struct cow {
 int weight;
 int smart;
 int id;
};
//-----------------------------
cow a[maxn],tmp[maxn];
int l1[maxn],l2[maxn];
int d[maxn][maxn],pre[maxn][maxn],ans[maxn];
int n = 0;
//-----------------------------
void _qsort(int l, int r, int k) {
 int i,j,x;
 cow tmp;
 i = l; j = r; 
 if (k==1) x = a[(l+r)/2].weight;
 else x = a[(l+r)/2].smart;
 do
 {
  if (k==1) 
  {
   while (a[i].weight<x) i++;
   while (x<a[j].weight) j--;
  }
  else
  {
   while (a[i].smart<x) i++;
   while (x<a[j].smart) j--;
  }
  if (i<=j)
  {
   tmp = a[i]; a[i] = a[j]; a[j] = tmp;
   i++; j--;
  }
 } while (i<=j);
 if (l<j) _qsort(l,j,k);
 if (i<r) _qsort(i,r,k);
} 
//-----------------------------
void solve() {
 _qsort(1,n,1);  // Sort according to weight
 for (int i=1; i<=n; i++) l1[i] = a[i].id; // get l1
 _qsort(1,n,2);  // Sort according to smart
 for (int i=1; i<=n; i++) l2[i] = a[n-i+1].id;  // get l2
 memset(d,0,sizeof(d));
 // LCS DP algorithm with trace back
 for (int i=1; i<=n; i++)
  for (int j=1; j<=n; j++)
   if (l1[i]==l2[j]) 
   {
    d[i][j] = d[i-1][j-1]+1;
    pre[i][j] = 3;
   }
   else 
   {
    if (d[i-1][j]>d[i][j-1]) 
    {
     d[i][j] = d[i-1][j];
     pre[i][j] = 1;
    }
    else 
    {
     d[i][j] = d[i][j-1];
     pre[i][j] = 2;
    }
   }
 int cnt = 0;
 int x = n, y = n;
 // Trace back for the answer
 while (x!=1 && y!=1)
 {
  if (pre[x][y]==3) 
  {
   if (cnt>=1)
   {
    // Check the condition before record the answer
    if (tmp[l1[x]].weight<tmp[ans[cnt]].weight && tmp[l1[x]].smart>tmp[ans[cnt]].smart)
     ans[++cnt] = l1[x];
   }
   else ans[++cnt] = l1[x];
   x-=1; y-=1;
  }
  else if (pre[x][y]==2) y-=1;
  else if (pre[x][y]==1) x-=1;
 }
 if (tmp[l1[x]].weight<tmp[ans[cnt]].weight && tmp[l1[x]].smart>tmp[ans[cnt]].smart && x==1)
  ans[++cnt] = l1[x];
 else 
  if (tmp[l2[y]].weight<tmp[ans[cnt]].weight && tmp[l2[y]].smart>tmp[ans[cnt]].smart) 
  ans[++cnt] = l2[y];
 cout << cnt << endl;
 for (int i=cnt; i>=1; i--) cout << ans[i] << endl;
}
//-----------------------------
int main() {
 while (!cin.eof()) 
 {
  n++;
  cin >> a[n].weight >> a[n].smart;
  a[n].id = n;
 }
 for (int i=1; i<=n; i++) tmp[i] = a[i];
 solve();
 return 0;
}
//-----------------------------