Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.FileNotFoundException;
- import java.io.FileReader;
- import java.io.PrintWriter;
- import java.util.*;
- import java.lang.Integer;
- class Worker {
- private static class Person {
- int index, sum;
- int startAuthority;
- int additionalAuthority;
- Person(int authority, int additionalAuthority) {
- this.startAuthority = authority;
- this.additionalAuthority = additionalAuthority;
- }
- Person(int index, int sum, int startAuthority, int additionalAuthority) {
- this.index = index;
- this.sum = sum;
- this.startAuthority = startAuthority;
- this.additionalAuthority = additionalAuthority;
- }
- }
- private ArrayList<Person> _array;
- private ArrayList<Boolean> _used;
- private PrintWriter _out;
- private int _authority;
- private ArrayList<Integer> _answer;
- Worker(String input, String output) throws FileNotFoundException {
- Scanner in = new Scanner(new FileReader(input));
- _out = new PrintWriter(output);
- int n = in.nextInt();
- _authority = in.nextInt();
- _array = new ArrayList<Person>(n);
- _used = new ArrayList<Boolean>(n);
- _answer = new ArrayList<Integer>(n);
- for (int i = 0; i < n; i++) {
- int authority = in.nextInt();
- int additionalAuthority = in.nextInt();
- _array.add(new Person(authority, additionalAuthority));
- _used.add(i, false);
- }
- in.close();
- }
- private void bringPositiveAuthority() {
- for (int i = 0; i < _array.size(); i++) {
- for (int j = 0; j < _array.size(); j++) {
- if ((!_used.get(j)) && _array.get(j).startAuthority <= _authority
- && _array.get(j).additionalAuthority >= 0) {
- _used.set(j, true);
- _authority += _array.get(j).additionalAuthority;
- _answer.add(j);
- }
- }
- }
- }
- private void bringNegativeAuthority() {
- ArrayList<Person> sortedArray = new ArrayList<Person>(_array.size());
- for (int i = 0; i < _array.size(); i++) {
- sortedArray.add(i,
- new Person(i, _array.get(i).startAuthority + _array.get(i).additionalAuthority,
- _array.get(i).startAuthority, _array.get(i).additionalAuthority));
- }
- Collections.sort(sortedArray, new Comparator<Person>() {
- @Override
- public int compare(Person o1, Person o2) {
- return Integer.valueOf(o1.sum).compareTo(o2.sum);
- }
- });
- for (int i = sortedArray.size() - 1; i >= 0; i--) {
- if (!_used.get(sortedArray.get(i).index) && _authority >= sortedArray.get(i).startAuthority) {
- _used.set(sortedArray.get(i).index, true);
- _authority += sortedArray.get(i).additionalAuthority;
- _answer.add(sortedArray.get(i).index);
- }
- }
- }
- void calc() {
- bringPositiveAuthority();
- bringNegativeAuthority();
- }
- void print() {
- _out.println(_answer.size());
- for (int i = 0; i < _answer.size(); i++) {
- _out.print(_answer.get(i) + 1 + " ");
- }
- _out.close();
- }
- }
- public class Main {
- public static void main(String[] args) throws FileNotFoundException {
- //Scanner input = new Scanner(System.in);
- Worker worker = new Worker("input.txt", "output.txt");
- worker.calc();
- worker.print();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement