Submission #1244417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244417		vibhas	Just Long Neckties (JOI20_ho_t1)	Java	9 / 100	1100 ms	90956 KiB

ho_t1

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class ho_t1{
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Necktie[]necktie_options = new Necktie[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n+1; i++){
            necktie_options[i] = new Necktie(Integer.parseInt(st.nextToken()), i);
        }
        Arrays.sort(necktie_options);
        int[]originals = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            originals[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(originals);
        // answered for if CEO took the smallest necktie option.
        TreeMap<Integer, Integer> first = new TreeMap<>();
        for(int i = 0; i < n; i++){
            int put = Math.max(0, necktie_options[i+1].length-originals[i]);
            if(first.containsKey(put)){
                first.put(put, first.get(put)+1);
            }else{
                first.put(put, 1);
            }
        }
        int[]ans = new int[n+1];
        ans[necktie_options[0].index] = first.lastKey();
        for(int i = 1; i <= n; i++){
            int last_difference = Math.max(0, necktie_options[i].length-originals[i-1]);
            if(first.get(last_difference) == 1){
                first.remove(last_difference);
            }else{
                first.put(last_difference, first.get(last_difference)-1);
            }
            int diff_now = Math.max(0, necktie_options[i-1].length - originals[i-1]);
            if(first.containsKey(diff_now)){
                first.put(diff_now, first.get(diff_now)+1);
            }else{
                first.put(diff_now, 1);
            }
            ans[necktie_options[i].index] = first.lastKey();
        }
        for(int i = 0; i <= n; i++){
            System.out.print(ans[i] + " ");
        }
        br.close();
    }
    static class Necktie implements Comparable<Necktie>{
        int length;
        int index;
        public Necktie(int a, int b){
            this.length = a;
            this.index = b;
        }
        public int compareTo(Necktie other){
            return this.length - other.length;
        }
    }
}

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 0 / 91