UVa 231 - Testing the CATCHER

// Longest Decreasing Sub sequence

// Accepted

#include<bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(false)
#define bfast cin.tie(0)
#define outs(x) cout << x << " "
#define outn(x) cout << x << "\n"
#define sf scanf
#define pf printf
#define nl puts("")
#define psb push_back

typedef long long LL;
typedef vector<int>vii;
typedef vector<LL>vll;

const int mod = 1000007;
const int high = 100;
const int inf = 2147483647;

vll Mseq , I;

int sol(int n)
{
    int i, len=0, lo=0, hi=0 , mid;

    I.clear();

    I.push_back(-inf);

    for(i=1; i<=n; i++)
    {
        I.push_back(inf);
    }

    for(i=0; i<n; i++)
    {
        lo=0;
        hi=len;

        while(lo <= hi)
        {
            mid = (lo+hi) / 2;

            if(I[mid] < Mseq[i]) lo=mid+1;
            else hi=mid-1;
        }

        len = max(lo, len);
        I[lo] = Mseq[i];
    }

    return len;
}

int main()
{
    fast;
    // error khai ken/
    int tc=1 , x;

    while(cin >> x)
    {
         if(x == -1) break;
         Mseq.clear();

         Mseq.push_back(x);

         while(cin >> x)
        {
            if(x == -1) break;
            Mseq.push_back(x);
        }

        if(tc != 1) cout << "\n";

        reverse(Mseq.begin() , Mseq.end());

        cout <<"Test #" << tc++ <<":"<< "\n" <<"  maximum possible interceptions: " << sol(Mseq.size()) << "\n";
    }

    return 0;
}