Uva - 231 - Testing the CATCHER

Problem: 231 - Testing the CATCHER

Explain: Longest Decreasing Subsequence


Code:
-------

/*
Algorithm: Longest Decreasing Seq.
Complexity: nlgn
*/
#include<stdio.h>
#include<limits.h>
#define S 1000000

int R[S]={0};/*Generated Table*/
int A[S] = {0};/*Input data*/
int Indx[S]= {0}; /*Index of the Table Element*/
int Pre[S]={0}; /*Previous Element*/

/*Complexity lg2^N*/
int BS(int v,int s,int e){
    int mid=0;
    while(s<=e){
         mid = s+((e-s)/2);
         /*Remove small*/
         if (R[mid]<=v){
              if (v<R[mid-1]|| v == R[mid-1])break;
              e = mid-1;
         }
         else if (v<R[mid]){
            if(R[mid+1]<v){mid=mid+1;break;}
            s = mid+1;
         }
    }
    return mid;
}


int main(){
    int i,v=0,j;
    int rc;
    int s,e,mid;/*Binary Search*/
    int N=1,flag;

    /*freopen("a.txt","r",stdin);*/

    A[0]=R[0] = INT_MAX;
    Indx[0] = 0;
    flag = 0;
    while(1){
       rc=1;
       for(i=1;;i++){
           scanf("%d",&A[i]);
           if ( A[i] == -1){ if ( i == 1) flag = 1; break;}
           v = A[i];
           if(v<=R[rc-1]){
              R[rc] = v;
              Indx[rc] = i;
              Pre[i] = Indx[rc-1];
              rc++;
           }
           else if(v>R[rc-1]){/*Binary Search*/
              mid = BS(v,1,rc-1);
              R[mid] = v;
              Indx[mid]= i;
              Pre[i] = Indx[mid-1];
            }
        }
        if(flag==1) break;
        if (N >1) printf("\n");
        printf("Test #%d:\n  maximum possible interceptions: %d\n",N++,rc-1);
        for(i=1;i<=N;i++) Pre[i]=0,Indx[i]=0,R[i]=0;
    }
    return 0;
}