Submission #1117542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117542		secretwood01	Global Warming (NOI13_gw)	Java	19 / 40	1045 ms	54584 KiB

gw

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

public class gw {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        int N = Integer.parseInt(br.readLine());
        Element [] Arr = new Element[N];
        Element[] TSet = new Element[N];
        //HashMap<Integer, Integer> HMap = new HashMap<Integer, Integer>();
        for (int i=0;i<N;i++) {
            Arr[i] = new Element(Integer.parseInt(br.readLine()), i); 
        }
        Arrays.sort(Arr);
        pw.println(bs(Arr));
        pw.close();
        br.close();
    }
    public static int bs(Element[] T) {
        int lo = 1;
        int hi = T.length;
		while (lo < hi) {
			int mid = lo + (hi - lo + 1) / 2;
			if (f(mid, T)) {
				lo = mid;
			} else {
				hi = mid - 1;
			}
		}
		return lo;
    }
    public static boolean f(int mid, Element[] T) {
        int islands = 0;
        int index = 0;
        boolean [] v = new boolean[T.length];
        while (islands<mid && index<T.length) {
            int currVal = T[index].val;
            while (index<T.length && T[index].val==currVal) {
                Element curr = T[index];
                v[curr.ind] = true;
                boolean left = curr.ind==0 || !v[curr.ind-1];
                boolean right = curr.ind==v.length-1 || !v[curr.ind+1];
                if (left&&right) islands++;
                boolean negLeft = curr.ind!=0 && v[curr.ind-1];
                boolean negRight = curr.ind!=v.length-1 && v[curr.ind+1];
                if (negLeft&&negRight) islands--;
                index++;
            }
        }
        return islands>=mid;
    }
}
class Element implements Comparable<Element> {
    int val;
    int ind;
    public Element(int val, int ind) {
        this.val = val;
        this.ind = ind;
    }
    public int compareTo(Element o) {
        return Integer.compare(o.val, val);
    }
    public Element clone() {
        return new Element(val, ind);
    }
    public boolean equals(Element o) {
        return val==o.val && ind==o.ind;
    }
}

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11