PROBLEM LINK:
Author: arnie8991
Tester: sandeep1103
Editorialist: arnie8991
DIFFICULTY:
EASY
PREREQUISITES:
Problem
We are to provide the order in which the children are going to receive their toys, based on certain conditions. Children having less number of toys will be preferred. If the children have the same number of toys, then we will decide on the basis of the number of storybooks that they have. If both storybooks and toys are equal then children with lower roll number will be preferred.
EXPLANATION:
The most simple approach is to store the inputs in the form of a 2-D array and then sort that array using a custom comparator function. Most languages support custom comparator function. In this editorial, the comparator is in Java. If Merge Sort is used for the operation, the time complexity is going to be O(NlogN).
SOLUTIONS:
Setter's Solution
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
Task solver = new Task();
int test = 1;
while(test-->0){
solver.solve(1, in, out);
}
out.close();
}
}
class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream));
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
public long nextLong() {
return Long.parseLong(next());
}
public Double nextDouble() {
return Double.parseDouble(next());
}
public float nextFloat() {
return Float.parseFloat(next());
}
}
class Task {
final long MOD = (int)Math.pow(10,9)+7;
public void solve(int testNumber, InputReader sc, PrintWriter out) {
int n = sc.nextInt();
List<Integer[]> info = new ArrayList<>();
for(int i = 0; i < n; i++){
Integer storybooks = sc.nextInt();
Integer toys = sc.nextInt();
info.add(new Integer[]{storybooks, toys, i});
}
solve(info);
}
public static void solve(List<Integer[]> info){
Collections.sort(info, new Comparator<Integer[]>() {
@Override
public int compare(Integer[] a, Integer[] b){
if (a[1]<b[1] || a[1] > b[1]) {
return Integer.compare(a[1], b[1]);
} else if (a[0] < b[0] || a[0] > b[0]){
return -Integer.compare(a[0], b[0]);
}else
return -Integer.compare(a[2], b[2]);
}
});
for(int i = 0; i < info.size(); ++i){
System.out.print(info.get(i)[2]+1+" ");
}
}
}