oj.uz

Submission #1117539

# Submission time Handle Problem Language Result Execution time Memory
1117539 2024-11-23T22:19:08 Z secretwood01 Global Warming (NOI13_gw) Java 11
19 / 40
 1000 ms 63688 KB 
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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 14576 KB Output is correct
2 Correct 70 ms 14560 KB Output is correct
3 Correct 62 ms 13488 KB Output is correct
4 Correct 66 ms 14160 KB Output is correct
5 Correct 67 ms 14268 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 23804 KB Output is correct
2 Correct 800 ms 23824 KB Output is correct
3 Correct 721 ms 23644 KB Output is correct
4 Correct 757 ms 24052 KB Output is correct
5 Correct 726 ms 23628 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 743 ms 25148 KB Output is correct
2 Correct 305 ms 23868 KB Output is correct
3 Correct 852 ms 24260 KB Output is correct
4 Correct 725 ms 24992 KB Output is correct
5 Correct 691 ms 24464 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1048 ms 63688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 62956 KB Time limit exceeded
2 Halted 0 ms 0 KB -