Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- struct book {
- int o_ind;
- int score;
- vector<int> libs;
- int ind_lib;
- };
- struct library{
- int o_ind;
- double val;
- int days;
- int bpday;
- vector<int> bs;
- int ind_book;
- };
- bool cmp(book a, book b) {
- if(a.score == b.score) return a.o_ind < b.o_ind;
- return a.score > b.score;
- }
- bool cmp_lib(library l1, library l2) {
- if(l1.val == l2.val) return l1.bs.size() < l2.bs.size();
- return l1.val > l2.val;
- }
- int main() {
- freopen("input.txt", "r", stdin);
- freopen("output2.txt", "w", stdout);
- int b, l ,d;
- cin >> b >> l >> d;
- vector<book> books(b);
- vector<library> libs_(l);
- for(int i = 0; i < b; ++ i) {
- int x;
- cin >> x;
- vector<int> v = {};
- books[i] = {i, x, v, 0};
- }
- vector< vector<int> > V(l);
- for(int i = 0; i < l; ++ i) {
- int n, days, nbsp;
- cin >> n >> days >> nbsp;
- int total_score = 0;
- vector<int> inds;
- for(int j = 0; j < n; ++ j) {
- int x;
- cin >> x;
- inds.push_back(x);
- total_score += books[x].score;
- }
- auto val = (double) (1.0 * total_score * nbsp / days);
- V.push_back(inds);
- libs_[i] = {i, val, days, nbsp, inds, 0};
- }
- sort(libs_.begin(), libs_.end(), cmp_lib);
- for(int i = 0; i < libs_.size(); ++ i) {
- for(auto e : libs_[i].bs)
- books[e].libs.push_back(i);
- }
- sort(books.begin(), books.end(), cmp);
- int curr_book = 0;
- vector<int> marked_lib(l, 0);
- vector<int> marked_book(b, 0);
- vector<int> out_libs;
- int total_sup = 0;
- vector< vector <int> > out_books;
- while(curr_book < b) {
- while(curr_book < b && marked_book[curr_book]) {
- curr_book++;
- // cout << curr_book;
- }
- if (curr_book == b) {
- break;
- }
- int indb = books[curr_book].o_ind;
- int valb = books[curr_book].score;
- int ind_lib = books[curr_book].ind_lib;
- vector<int> libs = books[curr_book].libs;
- for(int i = ind_lib; i < libs.size(); ++ i) {
- if(marked_lib[libs[i]] == 0) {
- marked_lib[libs[i]] = 1;
- int ind = libs[i];
- out_libs.push_back(libs_[ind].o_ind);
- out_books.push_back({});
- int days = libs_[ind].days;
- total_sup += days;
- int bpday = libs_[ind].bpday;
- vector<int> bs = libs_[ind].bs;
- int ind_book = libs_[ind].ind_book;
- vector<int> curr_day_books;
- int curr_ind_j = 0;
- vector<int> out_b;
- int cur_marked_n = 0;
- int bound = (d - total_sup) * bpday;
- for(int j = ind_book; j < bs.size(); ++j) {
- if(marked_book[bs[j]] == 0) {
- out_books.back().push_back(bs[j]);
- marked_book[bs[j]] = 1;
- cur_marked_n += 1;
- }
- if(cur_marked_n == bound) {
- curr_ind_j = j;
- break;
- }
- }
- libs_[ind].ind_book = curr_ind_j;
- }
- }
- curr_book += 1;
- }
- int output_n = 0;
- for (int i = 0; i < out_libs.size(); ++ i) {
- if (out_books[i].size() > 0) {
- output_n += 1;
- }
- }
- cout << output_n << "\n";
- for(int i = 0; i < out_libs.size(); ++ i) {
- if (out_books[i].size() == 0) {
- continue;
- }
- cout << out_libs[i] << " " << out_books[i].size() << endl;
- for(auto e : out_books[i])
- cout << e << " ";
- cout << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement