Problem

11/11

Biancaneve e N Nani

Problem

"Beh, non gnomi, ma una specie di punizione!", – pensò Biancaneve, cercando ancora una volta di addormentare i nani. Ne metterai giù uno – l'altro è già sveglio! E così tutta la notte.
 
Biancaneve ha n nani, e sono tutti molto diversi. Sa che ci vogliono tutti i minuti per far addormentare l'i-esimo nano, dopodiché dormirà esattamente due minuti. Aiuta Biancaneve a scoprire se riesce a riposare almeno un minuto quando tutti i nani dormono e, in tal caso, in quale ordine far addormentare i nani.
 
Ad esempio, supponiamo che ci siano solo due gnomi, a1 = 1, b1 = 10, a2 = 10, b2 = 20. Se Biancaneve inizia a mettere a letto prima il primo gnomo, le ci vorranno 10 minuti per mettere a letto il secondo uno a letto, e durante questo periodo si sveglierà il primo . Se inizia con il secondo nano, avrà il tempo di mettere a letto il primo e riposarsi per ben 10 minuti.
 
Inserisci i dati
La prima riga del file di input contiene il numero n (1 <= n <= 10000), la seconda riga contiene i numeri a1,a2,… un, terzo – numeri b1,b2,… bn (1 <= ai, bi <= 100000).
 
Uscita
Stampa sul file di output n numeri – ordine in cui mettere a letto gli gnomi. Se Biancaneve non riesce a riposare, stampa il numero -1.

Entra Uscita
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!