[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
        Collections.sort(solvedProblems, new SortByM());

        for (SolvedProblems prob : solvedProblems) {

    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> {

        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.


Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.