Module: Sorting with comparator


Problem

11/11

Snow White and N Dwarfs

Problem

“Well, not gnomes, but some kind of punishment!”, – thought Snow White, once again trying to put the dwarves to sleep. You will put one down – the other is already awake! And so all night.
 
Snow White has n dwarves, and they are all very different. She knows that it takes ai minutes to put the i-th dwarf to sleep, and after that he will sleep exactly bi minutes. Help Snow White find out if she can get at least a minute of rest when all the dwarves are asleep, and if so, in what order to put the dwarves to sleep.
 
For example, let's say there are only two gnomes, a1 = 1, b1 = 10, a2 = 10, b2 = 20. If Snow White starts putting the first gnome to bed first, then it will take her 10 minutes to put the second one to bed, and during this time the first one will wake up . If she starts with the second dwarf, then she will have time to put the first one to bed and get a whole 10 minutes of rest.
 
Input data
The first line of the input file contains the number n (1 <= n <= 10000), the second line contains the numbers a1,a2,… an, third – numbers b1,b2,… bn (1 <= ai, bi <= 100000).
 
Output
Print to the output file n numbers – order in which to put the gnomes to bed. If Snow White fails to rest, print the number -1.

Enter Output
2
1 10
10 20
2 1
(c) Grigoriev E., 2018

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Insert the missing code snippets
C++
Write the program below 
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 5;

struct dwarf {
    int a, b, i;
    dwarf() {}
    dwarf(int _a, int _i) {
        this->a = _a;
        this->i = _i;
    }
};

int n;
int k;
int c;
vector<dwarf>dwarfs(N);

bool cmp(dwarf a, dwarf b) {   
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        k += x;
        dwarfs.at(i) = dwarf(x, i + 1);
    }

    for (int i = 0; i < n; i++) {
        cin >> dwarfs.at(i).b;
        if (dwarfs.at(i).b - (k - dwarfs.at(i).a) <= 0)
            c++;
    }

    if (c == n) {
        cout << -1;
        return 0;
    }

    sort(dwarfs.begin(), dwarfs.end(), cmp);

    for (int i = 0; i < n; i++)
        cout << dwarfs.at(i).i << " ";

    return 0;
}

     

Program check result

To check the solution of the problem, you need to register or log in!