oj.uz

Submission #1117542

# Submission time Handle Problem Language Result Execution time Memory
1117542 2024-11-23T22:21:33 Z secretwood01 Global Warming (NOI13_gw) Java 11
19 / 40
 1000 ms 54584 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 77 ms 14428 KB Output is correct
2 Correct 71 ms 14088 KB Output is correct
3 Correct 66 ms 14376 KB Output is correct
4 Correct 72 ms 14308 KB Output is correct
5 Correct 72 ms 14756 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 721 ms 23052 KB Output is correct
2 Correct 794 ms 23544 KB Output is correct
3 Correct 734 ms 23452 KB Output is correct
4 Correct 708 ms 23556 KB Output is correct
5 Correct 744 ms 23600 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 807 ms 23680 KB Output is correct
2 Correct 323 ms 22996 KB Output is correct
3 Correct 861 ms 23648 KB Output is correct
4 Correct 725 ms 23864 KB Output is correct
5 Correct 713 ms 23696 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1045 ms 54584 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 1041 ms 54488 KB Time limit exceeded
2 Halted 0 ms 0 KB -