#define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; typedef long long ll; #define MAX 1000000000000000000; int n, k, N ; ll KON, b, h, tp, sum = MAX int pointer_max, end_n; int perm[13], used[13]; int used_hole[1000001]; struct STICKS { int h, n; ll p; bool operator < (STICKS &a) { return (this->h < a.h); } } st[1000001]; struct STICKSMAX { int h, n; ll p; bool operator < (STICKSMAX &a) { return (this->h > a.h); } } stmax[1000001]; struct TEMPRESULT { vectorhole; } tere[1000001]; struct RESULT { vectorhole; } re[1000001]; void SaveResult() { for (int i = 1; i <= k; i++) { re[i].hole = tere[i].hole; tere[i].hole.clear(); } } ll DiffHole(ll i) { return (i + 1)*(i + 1)*(i + 1) - i * i * i; } void SetKON() { ll sum_h = 0; for (int i = 1; i <= n; i++) sum_h += st[i].h; KON = DiffHole(sum_h /( b*1.5)); } void Compression() { int z = 0; for (int i = 1; i <= end_n; i++) { if (used_hole[i] == 0) { z++; continue; } used_hole[i - z] = used_hole[i]; } end_n -= z; } void SetSticks() { h = 0; if (pointer_max == 0) pointer_max++; for (int i = pointer_max + 1; i <= end_n; i++) { if (h + stmax[used_hole[i]].h >= b) continue; if (b - h + stmax[used_hole[i]].h == 1) { re[k].hole.push_back(stmax[used_hole[i]].n); used_hole[i] = 0; break; } re[k].hole.push_back(stmax[used_hole[i]].n); h += stmax[used_hole[i]].h; used_hole[i] = 0; } re[k].hole.push_back(stmax[used_hole[1]].n); used_hole[1] = 0; pointer_max--; } void SolveMaxH() { ll sum_h = 0; k = 0; end_n = n; sort(&stmax[1], &stmax[n + 1]); SetKON(); for (int i = 1; i <= n; i++) { used_hole[i] = i; sum_h += st[i].h; } // set used_hole pointer_max = sum_h / (b * 1.5); // calculated holes while (end_n){ k++; SetSticks(); Compression(); } } void SolveMin() { sort(&st[1], &st[n + 1]); SetKON(); h = 0; k = 1; int max_h = n, min_h = 1; for (int i = 1; i <= n; i++) { //if (N == n) break; if (N == n - 1 ) { if (h + st[min_h].h <= b) { re[k].hole.push_back(st[min_h].n); break; } if (st[min_h].p > KON) { k++; re[k].hole.push_back(st[min_h].n); break; } if (h == b) { k++; re[k].hole.push_back(st[min_h].n); break; } re[k].hole.push_back(st[min_h].n); break; } if (h + st[min_h].h < b) { re[k].hole.push_back(st[min_h].n); N++; h += st[min_h].h; min_h++; continue; } if (st[i].p > KON) { if (h + st[min_h].h < b) { re[k].hole.push_back(st[min_h].n); h += st[min_h].h; min_h++; N++; continue; } if (h + st[min_h].h == b) { re[k].hole.push_back(st[min_h].n); h = 0; k++; min_h++; N++; continue; } if (st[min_h].h >= b) { re[k].hole.push_back(st[min_h].n); h = 0; k++; min_h++; N++; continue; } k++; re[k].hole.push_back(st[min_h].n); h = st[min_h].h; min_h++; N++; continue; } re[k].hole.push_back(st[max_h].n); h = 0; k++; max_h--; N++; continue; } } void Test10() { ll h = 0; int t_k = 1; ll t_sum = 0; for (int i = 1; i <= n; i++) { if (i == n) { //last stick if (h + st[perm[i-1]].h <= b) { tere[t_k].hole.push_back(perm[i-1]); break; } if (st[perm[i-1] ].p > DiffHole(t_k)) { t_k++; tere[t_k].hole.push_back(perm[i-1]); break; } t_sum += st[perm[i-1]].p; tere[t_k].hole.push_back(perm[i-1]); break; } if (h + st[perm[i-1]].h < b) { tere[t_k].hole.push_back(perm[i-1]); h += st[perm[i-1]].h; continue; } if(h + st[perm[i - 1]].h == b) { tere[t_k].hole.push_back(perm[i - 1]); h = 0; t_k++; continue; } tere[t_k].hole.push_back(perm[i - 1]); h = 0; t_k++; t_sum += st[perm[i - 1]].p; } if (t_sum + t_k * t_k * t_k < sum) { k = t_k; SaveResult(); sum = k * k * k + t_sum; } for (int i = 1; i <= t_k; i++) { tere[i].hole.clear();} } void Total() { for (int i = 0; i < n; i++) perm[i] = i + 1; do { Test10(); } while (next_permutation(perm, perm + n)); } void Input() { FILE *in = fopen("sticks.in", "r"); fscanf(in, "%i %lld\n", &n, &b); for (int i = 1; i <= n; i++) { fscanf(in, "%i ", &st[i].h); st[i].n = i; stmax[i].n = i; stmax[i].h = st[i].h; } for (int i = 1; i <= n; i++) { fscanf(in, "%lld ", &st[i].p); } } void Output() { FILE *out = fopen("sticks.out", "w"); fprintf(out, "%i\n", k); for (int i = 1; i <= k; i++) { fprintf(out, "%i ", re[i].hole.size()); for (int j = 0; j < re[i].hole.size(); j++) fprintf(out, "%i ", re[i].hole[j]); fprintf(out, "\n"); } } int main() { Input(); if (n <= 10) { Total(); Output(); return 0; } if (n <= 100) { SolveMaxH(); Output(); return 0; } SolveMin(); Output(); return 0; }