Problem

11/11

Bạch Tuyết và N chú lùn

Problem

"Chà, không phải thần lùn, mà là một hình phạt nào đó!", – Bạch Tuyết nghĩ, một lần nữa cố gắng đưa những chú lùn vào giấc ngủ. Bạn sẽ đặt một cái xuống – người kia đã tỉnh rồi! Và cứ thế suốt đêm.
 
Bạch Tuyết có n chú lùn, và tất cả họ đều rất khác nhau. Cô ấy biết rằng phải mất ai phút để đưa người lùn thứ i vào giấc ngủ, và sau đó anh ta sẽ ngủ đúng hai phút. Hãy giúp Bạch Tuyết tìm hiểu xem liệu cô ấy có thể nghỉ ngơi ít nhất một phút khi tất cả những người lùn đã ngủ không, và nếu có, thì theo thứ tự nào để đưa những người lùn vào giấc ngủ.
 
Ví dụ: giả sử chỉ có hai thần lùn, a1 = 1, b1 = 10, a2 = 10, b2 = 20. Nếu Bạch Tuyết bắt thần lùn đầu tiên đi ngủ trước, thì cô ấy sẽ mất 10 phút để đặt thần lùn thứ hai. một người đi ngủ, và trong thời gian này người đầu tiên sẽ thức dậy . Nếu cô ấy bắt đầu với chú lùn thứ hai, thì cô ấy sẽ có thời gian để đưa chú lùn đầu tiên đi ngủ và được nghỉ ngơi trọn vẹn trong 10 phút.
 
Dữ liệu đầu vào
Dòng đầu tiên của tệp đầu vào chứa số n (1 <= n <= 10000), dòng thứ hai chứa các số a1,a2,… một, thứ ba – số b1,b2,… bn (1 <= ai, bi <= 100000).
 
Đầu ra
In ra tệp đầu ra n số – thứ tự để đặt các gnomes đi ngủ. Nếu Bạch Tuyết không thể nghỉ ngơi, hãy in ra số -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++
Nhập Đầu ra
2
1 10
10 20
2 1
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!