[Timus] 1100 Final Standings

Problem statement is here: http://acm.timus.ru/problem.aspx?space=1&num=1100

Carefully observe the sample output. Some points to note:

1. The output is sorted by M

2. But for same M the output is sorted by index it is seen in input.

3 5 comes before 26 4 and 26 4 comes before 22 4 so 26 4 is before 22 4 in the output.

Use of comparator makes the code easy.

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int n = in.nextInt();
        List<SolvedProblems> solvedProblems = new ArrayList<>(n);
        int i = 0;
        while (n-- > 0) {
            solvedProblems.add(new SolvedProblems(i, in.nextInt(), in
                    .nextInt()));
            i++;
        }
        Collections.sort(solvedProblems, new SortByM());

        for (SolvedProblems prob : solvedProblems) {
            out.println(prob);
        }
    }

    class SolvedProblems {
        int index, id, m;

        public SolvedProblems(int ind, int i, int j) {
            index = ind;
            id = i;
            m = j;
        }

        public String toString() {
            return id + " " + m;
        }
    }

    class SortByM implements Comparator<SolvedProblems> {

        @Override
        public int compare(SolvedProblems o1, SolvedProblems o2) {
            if (o1.m == o2.m) {
                return o1.index - o2.index;
            }
            return o2.m - o1.m;
        }
    }

Another way to solve this (left as an exercise) is to have an array of 101 elements and for each element create a dynamic data structure (like list or vector) which stores the id in the same order as seen in the input. Loop through the array in reverse and print the list.