#include using namespace std; // GLOBALS // struct stick { int64_t index; int64_t height; int64_t penalty; }; stick sticks_array_original[1100000]; stick sticks_array[1100000]; vector> holes; vector outputs; int64_t n, hole_depth = 0; int64_t number_of_holes = 1; int64_t total_penalty = 0; // PRIORITY FORMULA BALANCED // int64_t priority_formula_balanced(stick& a) { return a.penalty - a.height; } // PRIORITY FORMULA HEIGHT // int64_t priority_formula_height(stick& a) { return -a.height; } // PRIORITY FORMULA REVERSED // int64_t priority_formula_reversed(stick& a) { return a.height - a.penalty; } // PRIORITY FORMULA PENALTY int64_t priority_formula_penalty(stick& a) { return a.penalty; } // PRIORITY FORMULA HEIGHT REVERSED int64_t priority_formula_height_reversed(stick& a) { return a.height; } // PRIORITY FORMULA PENALTY REVERSED int64_t priority_formula_penalty_reversed(stick& a) { return -a.penalty; } // PRIORITY FORMULA RATIO int64_t priority_formula_ratio(stick& a) { return a.penalty / a.height; } // PRIORITY FORMULA RATIO REVERSED int64_t priority_formula_ratio_reversed(stick& a) { return a.height / a.penalty; } vector func_arrays = { priority_formula_balanced, priority_formula_height, priority_formula_reversed, priority_formula_penalty, priority_formula_height_reversed, priority_formula_penalty_reversed, priority_formula_ratio, priority_formula_ratio_reversed }; // RETURN GRADE // int64_t get_grade() { return number_of_holes * number_of_holes * number_of_holes + total_penalty; } void add_output_string() { // OUTPUT STRING CREATION // string output_string = ""; output_string += to_string(number_of_holes) + '\n'; for(int64_t i = 0; i < number_of_holes; i++) { output_string += to_string(holes[i].size()) + ' '; for(int64_t j = 0; j < holes[i].size(); j++) { output_string += to_string(holes[i][j]) + ' '; } output_string += '\n'; } outputs.push_back(output_string); } //////////////////////////////////// // CALCULATION ( MULTIPLE STEPS ) // //////////////////////////////////// bool calculate(int64_t function_index) { // SORT BY PRIORITY // sort(sticks_array, sticks_array + n, [function_index](stick& a, stick& b) { return func_arrays[function_index](a) > func_arrays[function_index](b); } ); // CALCULATE OUTPUT // holes.clear(); number_of_holes = 1; total_penalty = 0; int64_t index_od_pozadi = n - 1; int64_t current_hole_fillup = 0; int64_t current_penalty = 0; for(int64_t i = 0; i < n; i++) { if(index_od_pozadi < i) break; if(current_hole_fillup >= hole_depth) { number_of_holes++; total_penalty += current_penalty; current_penalty = 0; current_hole_fillup = 0; } int64_t hole_index = number_of_holes - 1; if(holes.empty() || holes.size() < number_of_holes) { vector poop; holes.push_back(poop); } // IF STICK DOESNT STICK OUT OF HOLE // if(current_hole_fillup + sticks_array[i].height < hole_depth) { holes[hole_index].push_back(sticks_array[i].index); current_hole_fillup += sticks_array[i].height; current_penalty = sticks_array[i].penalty; // IF IT DOES // } else { holes[hole_index].push_back(sticks_array[index_od_pozadi].index); current_hole_fillup += sticks_array[i].height; current_penalty = sticks_array[index_od_pozadi].penalty; index_od_pozadi--; i--; } } add_output_string(); return true; } //////////////////////// // LINEAR CALCULATION // //////////////////////// bool linear_calculate() { // CALCULATE OUTPUT // number_of_holes = 1; total_penalty = 0; int64_t current_hole_fillup = 0; int64_t current_penalty = 0; for(int64_t i = 0; i < n; i++) { holes[i].clear(); } for(int64_t i = 0; i < n; i++) { if(current_hole_fillup >= hole_depth) { number_of_holes++; total_penalty += current_penalty; current_penalty = 0; current_hole_fillup = 0; } int64_t hole_index = number_of_holes - 1; holes[hole_index].push_back(sticks_array[i].index); current_hole_fillup += sticks_array[i].height; current_penalty = sticks_array[i].penalty; } return true; } int main() { // FREOPEN // freopen("sticks.in", "r", stdin); freopen("sticks.out", "w", stdout); /////////// // INPUT // /////////// cin >> n >> hole_depth; for(int64_t i = 0; i < n; i++) { sticks_array[i].index = i + 1; cin >> sticks_array[i].height; sticks_array_original[i].index = sticks_array[i].index; sticks_array_original[i].height = sticks_array[i].height; } for(int64_t i = 0; i < n; i++) { cin >> sticks_array[i].penalty; sticks_array_original[i].penalty = sticks_array[i].penalty; } // CALCULATION, WE DO THIS WITH MULTIPLE FUNCTIONS AND GET BEST GRADE // int64_t smallest_grade = -1; int64_t smallest_grade_index = 0; if(n > 10) { int64_t function_n = func_arrays.size(); for(int i = 0; i < function_n; i++) { calculate(i); int64_t grade = get_grade(); if(grade < smallest_grade || smallest_grade == -1) { smallest_grade_index = i; smallest_grade = grade; } if(i != function_n - 1) { copy_n(sticks_array_original, n, sticks_array); } } } else { for(int i = 0; i < n; i++) { vector funny; funny.reserve(10); holes.push_back(funny); } int64_t i = 0; sort(sticks_array, sticks_array + n, [](stick& a, stick& b) { return a.index < b.index; }); while(next_permutation(sticks_array, sticks_array + n, [](stick& a, stick& b) { return a.index < b.index; })) { linear_calculate(); int64_t grade = get_grade(); if(grade < smallest_grade || smallest_grade == -1) { add_output_string(); smallest_grade_index = i; smallest_grade = grade; i++; } } } //////////// // OUTPUT // //////////// cout << outputs[smallest_grade_index] << endl; }