CodeForces Problem Survival of the Weakest (Easy) Round 862 Div 2
Question
I wrote some code and even read the editorial and my code works for the first 4 given test cases but fails the 5th one. I would try to see what is wrong but the test case is very big.
My Work
Code in Java:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Survival_of_the_Weakest_Easy {
public static void main(String[] args) throws IOException {
BufferedReader r = new BufferedReader(
new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(r.readLine());
int N = Integer.parseInt(st.nextToken());
Pair[] arr = new Pair[N];
st = new StringTokenizer(r.readLine());
for (int i = 0; i < N; i++){
arr[i] = new Pair(Integer.parseInt(st.nextToken()), -1);
}
Arrays.sort(arr);
for (int i = 0; i < N; i++){
arr[i].pointer = i + 1;
}
PriorityQueue<Pair> pq = new PriorityQueue<>();
int add = 0;
for (int i = 0; i < N - 1; i++){
add += arr[0].val * Math.pow(2, arr.length - 1);
int sub = arr[0].val;
for (int j = 0; j < arr.length; j++){
arr[j].val -= sub;
}
pq.clear();
Pair[] tmp = new Pair[arr.length - 1];
for (int j = 0; j < arr.length - 1; j++){
pq.add(new Pair(arr[j].val + arr[arr[j].pointer].val, j));
}
for (int j = 0; j < tmp.length; j++){
Pair p = pq.poll();
tmp[j] = p.clone();
arr[p.pointer].pointer++;
if (arr[p.pointer].pointer < arr.length){
pq.add(new Pair(arr[p.pointer].val + arr[arr[p.pointer].pointer].val, p.pointer));
}
}
arr = tmp;
for (int j = 0; j < arr.length; j++){
arr[j].pointer = j + 1;
}
}
System.out.println((int) (arr[0].val + (add) % (Math.pow(10, 9) + 7)));
}
public static class Pair implements Comparable<Pair>{
int val, pointer;
public Pair(int val, int pointer){
this.val = val;
this.pointer = pointer;
}
public int compareTo(Pair p){
return Integer.compare(val, p.val);
}
public Pair clone(){
Pair tmp = new Pair(val, pointer);
return tmp;
}
}
}