11224 - Let's swim!

[mario]

It turned out that there was a hole in my algorithm. Actually two of them
Last input that TimeString posted helped me find one. The other hole was at the time to find what medal would get Gustavo in the finals. Well thanks for the help you guys.

[sith]

Hello
I'we got WA

My solution works properly for all cases from this thread. But I am getting WA

Code: Select all

import java.io.*;
import java.util.*;

class Main {

     public static void main(String[] args) {

         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

         BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
         Scanner scanner = new Scanner(reader);

         try {

             int cases = scanner.nextInt();
             for (int i = 1; i <= cases; i++) {
                 int competitors = scanner.nextInt();
                 int rank = scanner.nextInt();
                 Set<Competitor> competitorSet = new TreeSet<Competitor>();
                 List<Competitor> competitorList = new ArrayList<Competitor>();

                 Integer[] timesArray = new Integer[competitors-1];

                 IntegerComparator comparator = new IntegerComparator();
                 PriorityQueue<Integer> times = new PriorityQueue<Integer>(competitors, comparator);


                 for (int j = 0; j < competitors - 1; j++) {
                     Competitor e = new Competitor(scanner.nextInt(), scanner.nextLine());

                     timesArray[j] = e.time;
                     competitorList.add(e);


                 }



                 int timeSize = timesArray.length;
                 if (timeSize>7) {
                     timeSize = 7;
                 }

                 Arrays.sort(timesArray,comparator);
                 times.addAll(Arrays.asList(timesArray).subList(0, timeSize));
                 Collections.sort(competitorList);
                 competitorList.subList(0, timeSize);

                 if (rank==1) {

                     if (competitorList.get(timeSize -1).time -competitorList.get(timeSize -2).time==1) {
                         times.add(competitorList.get(timeSize - 1).time + 1);
                     }

                 }

                 competitorSet.addAll(competitorList);


                 Result result = new Result();
                 while (times.size() > 0) {

                     Integer gustavoTime = times.poll();
                     Competitor gustavo = new Competitor(rank, gustavoTime);
                     competitorSet.add(gustavo);
                     Result tmp = checkTime(competitorSet, gustavo, rank);


                     result = getNewResult(result, tmp);

                     if (result.semifinalResult<=8&&result.finalResult <= 3 && rank > 3) {
                         break;
                     }

                     Integer nextTime = times.peek();
                     if (nextTime == null) {
                         continue;
                     }
                     if (gustavoTime - nextTime > 1) {
                         gustavo.time--;
                         competitorSet.remove(gustavo);
                         competitorSet.add(gustavo);

                         tmp = checkTime(competitorSet, gustavo, rank);

                         result = getNewResult(result, tmp);


                         if (result.semifinalResult<=8&&result.finalResult <= 3 && rank > 3) {
                             break;
                         }

                         competitorSet.remove(gustavo);
                     }


                 }

                 writer.write("Case #" + i + ":\n");
                 writer.write("Gustavo should be #" + result.semifinalResult + " during the qualification to achieve position #" + result.finalResult + " in the final.\n");


             }

             writer.flush();
         } catch (IOException e) {
             e.printStackTrace();
         }


     }

    private static Result getNewResult(Result result, Result tmp) {

        if (tmp.finalResult<result.finalResult) {

            result = tmp;

        }
        return result;
    }

    private static Result checkTime(Set<Competitor> competitorSet, Competitor gustavo, int rank) {
        Result tmp=new Result(0,0);

        int lastMedalRank=0;
        for (Competitor competitor : competitorSet) {

            if (competitor.equals(gustavo)) {
                if (tmp.finalResult < 3 && competitor.rank <= 3) {

                    switch (tmp.finalResult) {
                        case 0:
                            tmp.finalResult = 1;
                            break;
                        case 2:
                            tmp.finalResult = gustavo.rank;
                            break;
                        default:
                            tmp.finalResult = gustavo.rank < lastMedalRank ? 1 : 2;

                    }


                } else {
                    tmp.finalResult++;

                }

                tmp.semifinalResult++;

                break;
            }


            if (competitor.rank < rank) {
                lastMedalRank = competitor.rank;
                tmp.finalResult++;
            }
            tmp.semifinalResult++;

        }
        return tmp;
    }


    static class Competitor implements Comparable<Competitor>{
        int rank, time;

        Competitor(int rank, String time) {
            this.rank = rank;
            StringTokenizer tokenizer = new StringTokenizer(time,": ");
            this.time = Integer.parseInt(tokenizer.nextToken())*60*100+Integer.parseInt(tokenizer.nextToken())*100+Integer.parseInt(tokenizer.nextToken());
        }

        public Competitor(int rank, Integer time) {
            this.rank = rank;
            this.time = time;
        }

        @Override
        public int compareTo(Competitor o) {
            int compare = time - o.time;
            if (compare==0) {
                return rank - o.rank;
            }
            return compare;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Competitor that = (Competitor) o;

            if (rank != that.rank) return false;

            return true;
        }

        @Override
        public int hashCode() {
            return rank;
        }

        @Override
        public String toString() {
            return "Competitor{" +
                    "rank=" + rank +
                    ", time=" + time +
                    '}';
        }
    }
    static class Result   {
        int semifinalResult = Integer.MIN_VALUE;
        int finalResult= Integer.MAX_VALUE;

        Result() {
        }

        Result(int semifinalResult, int finalResult) {
            this.semifinalResult = semifinalResult;
            this.finalResult = finalResult;
        }

        @Override
        public String toString() {
            return "Result{" +
                    "semifinalResult=" + semifinalResult +
                    ", finalResult=" + finalResult +
                    '}';
        }
    }
    private static class IntegerComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    }
}

[brianfry713]

Doesn't match the sample I/O.