Problem

11/11

Blanche-Neige et les nains N

Problem

"Eh bien, pas des gnomes, mais une sorte de punition!", – pensa Blanche-Neige, essayant une fois de plus d'endormir les nains. Vous en poserez un – l'autre est déjà réveillé ! Et ainsi toute la nuit.
 
Blanche-Neige a n nains, et ils sont tous très différents. Elle sait qu'il faut ai minutes pour endormir le ième nain, et après cela il dormira exactement 2 minutes. Aidez Blanche-Neige à découvrir si elle peut se reposer au moins une minute lorsque tous les nains sont endormis, et si oui, dans quel ordre endormir les nains.
 
Par exemple, disons qu'il n'y a que deux gnomes, a1 = 1, b1 = 10, a2 = 10, b2 = 20. Si Blanche-Neige commence à coucher le premier gnome en premier, alors il lui faudra 10 minutes pour mettre le second un au lit, et pendant ce temps le premier se réveillera. Si elle commence par le deuxième nain, elle aura alors le temps de mettre le premier au lit et de se reposer pendant 10 minutes.
 
Données d'entrée
La première ligne du fichier d'entrée contient le nombre n (1 <= n <= 10000), la deuxième ligne contient les nombres a1,a2,… un, troisième – nombres b1,b2,… milliards (1 <= ai, bi <= 100000).
 
Sortie
Imprimer dans le fichier de sortie n nombres – ordre dans lequel mettre les gnomes au lit. Si Blanche-Neige ne parvient pas à se reposer, imprimez le chiffre -1.

Entrez
Sortie
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!