Problem

11/11

Branca de Neve e N anões

Problem

“Bem, não gnomos, mas algum tipo de punição!”, – pensou Branca de Neve, mais uma vez tentando fazer os anões dormirem. Você vai colocar um para baixo – o outro já está acordado! E assim a noite toda.
 
Branca de Neve tem anões n, e eles são todos muito diferentes. Ela sabe que leva ai minutos para colocar o i-ésimo anão para dormir, e depois disso ele vai dormir exatamente bi minutos. Ajude Branca de Neve a descobrir se ela consegue pelo menos um minuto de descanso enquanto todos os anões estão dormindo e, em caso afirmativo, em que ordem colocar os anões para dormir.
 
Por exemplo, digamos que haja apenas dois gnomos, a1 = 1, b1 = 10, a2 = 10, b2 = 20. Se Branca de Neve começar a colocar o primeiro gnomo na cama primeiro, ela levará 10 minutos para colocar o segundo um para a cama, e durante este tempo o primeiro vai acordar. Se ela começar com o segundo anão, terá tempo de colocar o primeiro na cama e descansar 10 minutos inteiros.
 
Dados de entrada
A primeira linha do arquivo de entrada contém o número n (1 <= n <= 10000), a segunda linha contém os números a1,a2,… um, terceiro – números b1,b2,… bn (1 <= ai, bi <= 100000).
 
Saída
Imprimir no arquivo de saída n números – ordem em que colocar os gnomos para dormir. Se Branca de Neve não descansar, imprima o número -1.

Entrar Saída
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!