Submission #1244435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244435		vibhas	Just Long Neckties (JOI20_ho_t1)	Java	9 / 100	1098 ms	121440 KiB

ho_t1

/*
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class JOI_20_Neckties{
    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);
        List<Integer> originals = new ArrayList<>();
        // int[]originals = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++){
            // originals[i] = Integer.parseInt(st.nextToken());
            originals.add(Integer.parseInt(st.nextToken()));
        }
        // Arrays.sort(originals);
        Collections.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.get(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.get(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.get(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;
        }
    }
}

 */
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

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());
        int[]necktie_options = new int[n+1];
        TreeMap<Integer, Set<Integer>> option_indices = new TreeMap<>(); //<length, list of indices> Array A[i]
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n+1; i++){
            necktie_options[i] = Integer.parseInt(st.nextToken());
            if(option_indices.containsKey(necktie_options[i])){
                option_indices.get(necktie_options[i]).add(i);
            }else{
                Set<Integer>ts = new HashSet<>();
                ts.add(i);
                option_indices.put(necktie_options[i], ts);
            }
        }
        Arrays.sort(necktie_options);// sorting A[i], and remembering indices
        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); // neck ties of the employees as they come in.

        // analyzing the case the CEO chooses the smallest tie
        TreeMap<Integer, Integer> first = new TreeMap<>();
        for(int i = 0; i < n; i++){
            int put = Math.max(0, necktie_options[i+1]-originals[i]);
            if(first.containsKey(put)){
                first.put(put, first.get(put)+1);
            }else{
                first.put(put, 1);
            }
        }
        int[]ans = new int[n+1];
        for(int index : option_indices.get(option_indices.firstKey())){
            ans[index] = first.lastKey();
        }
        int start = option_indices.get(option_indices.firstKey()).size();
        // found answer if CEO takes any tie of smallest size
        // now, iterate through the next indices.
        while(start <= n){
            int last_diff = necktie_options[start]-originals[start-1];
            last_diff = Math.max(last_diff, 0);
            if(first.get(last_diff) == 1){
                first.remove(last_diff);
            }else{
                first.put(last_diff, first.get(last_diff)-1);
            }
            int curr_diff = necktie_options[start-1]-originals[start-1];
            curr_diff = Math.max(curr_diff, 0);
            if(first.containsKey(curr_diff)){
                first.put(curr_diff, first.get(curr_diff)+1);
            }else{
                first.put(curr_diff, 1);
            }
            int answer = first.lastKey();
            for(int index : option_indices.get(necktie_options[start])){
                ans[index] = answer;
            }
            start+=option_indices.get(necktie_options[start]).size();
        }
        PrintWriter pw = new PrintWriter(System.out);
        for(int i = 0; i <= n; i++){
            pw.print(ans[i] + " ");
        }
        br.close();
        pw.close();
    }
}

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