Problem

11/11

سفید برفی و N کوتوله

Problem

"خب، نه آدمک ها، بلکه نوعی مجازات!"، – سفید برفی فکر کرد که یک بار دیگر سعی می کند کوتوله ها را بخواباند. یکی را می گذارید – دیگری قبلاً بیدار است! و به همین ترتیب تمام شب.
 
سفید برفی n کوتوله دارد و همه آنها بسیار متفاوت هستند. او می‌داند که برای خواباندن کوتوله i‌ام، چند دقیقه طول می‌کشد و پس از آن دقیقاً دو دقیقه خواهد خوابید. به سفید برفی کمک کنید تا بفهمد آیا می‌تواند حداقل یک دقیقه استراحت کند وقتی همه کوتوله‌ها می‌خوابند، و اگر چنین است، به چه ترتیبی کوتوله‌ها را بخوابانند.
 
به عنوان مثال، فرض کنید فقط دو گنوم وجود دارد، a1 = 1، b1 = 10، a2 = 10، b2 = 20. اگر سفید برفی ابتدا اولین گنوم را به رختخواب بگذارد، آنگاه 10 دقیقه طول می کشد تا دومی را بگذارد. یکی به رختخواب می رود و در این مدت نفر اول بیدار می شود. اگر او با گنوم دوم شروع کند، آنگاه زمان خواهد داشت که اولی را بخواباند و 10 دقیقه کامل استراحت کند.
 
داده های ورودی
خط اول فایل ورودی حاوی عدد n (1 <= n <= 10000)، خط دوم شامل اعداد a1,a2,… an، سوم – اعداد b1,b2,… bn (1 <= ai، bi <= 100000).
 
خروجی
پرینت در فایل خروجی n عدد – ترتیب قرار دادن کوتوله ها در رختخواب. اگر سفید برفی نتواند استراحت کند، عدد -1 را چاپ کنید.

<بدن>
وارد کنید خروجی
2
1 10
10 20
2 1
(ج) گریگوریف ای.، 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!