OJ Board

Code: Select all

6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900

Code: Select all

1000 4000
1100 3000
6000 2100
6000 2000
500 2000
2000 1900
8000 1400
6008 1300
6000 1200

Code: Select all

1 1
1 2
1 9998
1 9999
1 10000
2 1
2 2
2 9998
2 9999
2 10000
9998 1
9998 2
9998 9998
9998 9999
9998 10000
9999 1
9999 2
9999 9998
9999 9999
9999 10000
10000 1
10000 2
10000 9998
10000 9999
10000 10000
1 1
2 1
9998 1
9999 1
10000 1
1 2
2 2
9998 2
9999 2
10000 2
1 9998
2 9998
9998 9998
9999 9998
10000 9998
1 9999
2 9999
9998 9999
9999 9999
10000 9999
1 10000
2 10000
9998 10000
9999 10000
10000 10000

Code: Select all

5
5
9
38
34
30

/////
1 10000
2 9999
9998 9998
9999 2
10000 1

Code: Select all

import java.io.IOException;
import java.util.StringTokenizer;

class Main {

	void work() {
		String line;
		StringTokenizer st;
		Elephant[] bunch = new Elephant[1010];
		int n = 0;
		while ((line = readLine()) != null) {
			if(line.length()==0) continue;
			st = new StringTokenizer(line);
			bunch[n++] = new Elephant(n, parseInt(st
					.nextToken()), parseInt(st.nextToken()));
		}
		// sort them first
		for (int i = 0; i < n; i++) {
			for (int j = n - 1; j > i; j--) {
				if (bunch[j].compare(bunch[j-1]) < 0) {
					Elephant tmp = bunch[j];
					bunch[j] = bunch[j - 1];
					bunch[j - 1] = tmp;
				}
			}
		}
		if (n == 0) {
			System.out.println(0);
		} else if (n == 1) {
			System.out.println("1\n1");
		} else {
			int maxLen = 0;
			int lastIndex = -1;
			bunch[0].prev = -1;
			bunch[0].lensofar = 1;
			for (int i = 1; i < n; i++) {
				int prevIndex = -1;
				int max = 0;
				for (int j = 0; j < i; j++) {
					if (bunch[j].w < bunch[i].w && bunch[j].s > bunch[i].s) {
						if (bunch[j].lensofar > max) {
							max = bunch[j].lensofar;
							prevIndex = j;
						}
					}
					bunch[i].prev = prevIndex;
					bunch[i].lensofar = max + 1;
					if (bunch[i].lensofar > maxLen) {
						maxLen = bunch[i].lensofar;
						lastIndex = i;
					}
				}
			}
			System.out.print(maxLen);
			StringBuffer res = new StringBuffer();
			for (int i = 0; i < maxLen; i++) {
				res.insert(0, bunch[lastIndex].num);
				res.insert(0, '\n');
				lastIndex = bunch[lastIndex].prev;
			}
			System.out.println(res);
		}
	}

	private int parseInt(String s) {
		// what if s.length() == 0 ?
		int result = 0;
		int sign = (s.charAt(0) == '-') ? -1 : 1;
		if (sign == -1)
			s = s.substring(1);
		int i = 0, max = s.length();
		if (max > 0) {
			while (i < max) {
				result *= 10;
				result += s.charAt(i++) - 48;
			}
		}
		return sign * result; // could be 0 if not an integer
	}

	private String readLine() {
		StringBuffer sb = new StringBuffer("");
		int b = 0;
		while (b != '\n' && b >= 0) {
			try {
				b = System.in.read();
			} catch (IOException e) {
				return null;
			}
			if (b != '\r' && b != '\n' && b >= 0)
				sb.append((char) b);
		}
		if (sb.length() == 0 && b < 0)
			return null;
		return sb.toString().trim();
	}

	public static void main(String args[]) {
		Main myWork = new Main();
		myWork.work();
	}
}

class Elephant {
	int num, w, s, prev, lensofar;

	Elephant(int num, int w, int s) {
		this.num = num;
		this.w = w;
		this.s = s;
		prev = -1;
		lensofar = 1;
	}

	public int compare(Elephant e2){
		if(w == e2.w){
			return e2.s - s;
		}
		else{
			return w - e2.w;
		}
	}

	public String toString() {
		return w + " " + s;
	}
}

Code: Select all

Program elefantes(input,output);
Const numEle = 999;

Type
	tElefante = record
			w: integer;
			iq: integer;
			num: integer;
		     end;
	tElefantes = array [0..numEle] of tElefante;


Var 
    a: tElefantes;
    prev,opt,opt_i: array [0..numEle+1] of integer;
    n,m,totales,w,iq : integer;
    f: array [0..numEle] of integer;

Function buscar(w:integer):integer;
Var l,r,k:integer;
Begin
    l := 1;
    r := m;
    while (l <= r) do 
	begin
        	k := (l+r) div 2;
        	if (w > opt[k]) then l := k+1
        	else r := k-1;
    	end;
    buscar := l;
End;


Procedure resolver();
Var  wk,j,i :integer;
Begin
    m := 1;
    opt[1] := a[0].w;
    opt_i[1] := 0;
    for i := 1 to totales-1 do
    Begin
        wk := a[i].w;
        j := buscar(wk);
        if (m < j) then 
		begin
            		m := m + 1;
            		opt[m] := wk;
            		opt_i[m] := i;
            		prev[i] := opt_i[m-1];
		end
        else begin
            if (wk < opt[j]) then begin
                opt[j] := wk;
                opt_i[j] := i;
                prev[i] := opt_i[j-1];
            	end;
        end;
    end;

    j := m-1;
    i := opt_i[m];
    while (j >= 0) do begin
        f[j] := i;
        i := prev[i];
        j := j - 1;
    end;

    writeln(m);
    for i:=0 to m-1 do writeln (a[f[i]].num);
		
end;



Procedure quicksort(var a:tElefantes;iz,de:integer);
var i,j,x:integer;
    aux:tElefante;
    porpeso:boolean;
begin
porpeso := TRUE;

i:=iz;
j:=de;

if (a[i].iq = a[j].iq) then porpeso := FALSE;

if porpeso then
	begin
	x:=a[(iz+de)div 2].iq;
	repeat
		while (a[i].iq > x) and (i<de) do i:=i+1;
		while (a[j].iq < x) and (j>iz) do j:=j-1;
		if i<=j then
			begin
			aux := a[i];
			a[i] := a[j];
			a[j] := aux;
			i:=i+1;
			j:=j-1;
			end;
	until i>j;
		if iz<j then quicksort(a,iz,j);
		if i < de then quicksort(a,i,de);
	end

else begin
	x:=a[(iz+de)div 2].w;
	repeat
		while (a[i].w < x) and (i<de) do i:=i+1;
		while (a[j].w > x) and (j>iz) do j:=j-1;
		if i<=j then
			begin
			aux := a[i];
			a[i] := a[j];
			a[j] := aux;
			i:=i+1;
			j:=j-1;
			end;
		until i>j;
		if iz< j then quicksort(a,iz,j);
		if i < de then quicksort(a,i,de);
	end;

end;


begin
     n:=0;  totales := 0;w:= 0; iq := 0;
    read(w);
    read(iq);

    while (n<1000) do
	begin
	if (w<>0) or (iq<>0) then 
		begin
       	 	a[totales].iq := iq;
		a[totales].w := w;
        	a[totales].num := n+1;
		totales := totales + 1;		
		end;
	read(w);
	read(iq);
       	n:=n+1;
    end;
  
    if (totales > 0) then begin
        quicksort(a,0,n-1);
	resolver();
    end;

end.