#include # define endl '\n' # define clr(x,a) memset(x,a,sizeof(x)) # define vi vector # define all(a) a.begin(), a.end() # define deb(x) cout<<#x<<"=="<='0') num = num * 10 + cc - '0'; return num; } inline void put_ll(ll x){ char cc; int br; if(x == 0){ *pos = '0'; *pos++; } else{ br = 0; while(x > 0){ cc = x%10+'0'; x/=10; niz_c[++br] = cc; } for(int i = 1; i <= br/2; i++) swap(niz_c[i], niz_c[br-i+1]); for(int i = 1; i <= br; i++){ *pos = niz_c[i]; *pos++; } } *pos = ' '; *pos++; } inline ll na3(ll x){return x*x*x;} ///__________________________ int n, nstare, najmanji_h=1e8, indeks, ids; ///0 je trenutni, 1 je final ll dubina[2][mxN], score[2] ={inf, inf}, k[2], nove_dubine[mxN], b, kolko_viri, minimalni, spi, dubi, dubj, delta_score; //dubina svake rupe vi rupa[2][mxN]; //indeksi stapova u rupi set> set_rupa; //slobodno mesta, id rupe set> :: iterator it; priority_queue > qju; pair par; pair tren_top; struct Stap{ ll p; int h, id; }stapovi[mxN]; struct trojka_stare_rupe{ ll penalti; int indeks_rupe, indeks_stapa; }stare_rupe[mxN], pomsr; struct dvojka_nove_rupe{ ll zauzeto; int indeks_rupe; bool operator <(const dvojka_nove_rupe &x)const{ return x.zauzeto < zauzeto; } }pomnr; priority_queue> pq_prostor; priority_queue pq_rupa; //pokazuje na nove rupe, i na topu je ona u kojoj je najmanje zauzeto0 bool cmp_stapovi_h_veci(Stap x, Stap y){return x.h > y.h;} bool cmp_stapovi_h_plus_p(Stap x, Stap y){return ((x.h > y.h+10) or (x.h <= y.h+10 and x.h > y.h and const_pea*x.p < y.p));} bool cmp_stapovi_penalty(Stap x, Stap y){return x.p < y.p;} bool cmp_id(Stap x, Stap y){return x.id < y.id;} bool cmp_sr_penalty(trojka_stare_rupe x, trojka_stare_rupe y){return x.penalti > y.penalti;} void unos(){ freopen("sticks.in", "r", stdin); fread(buffer, 1, LIMIT, stdin); pos=buffer; n = getll(); b = getll(); for(int i = 1; i <= n; i++){ stapovi[i].h = getll(); stapovi[i].id = i; najmanji_h = min(stapovi[i].h, najmanji_h); } for(int i = 1; i <= n; i++) stapovi[i].p = getll(); } void ispis(){ deb(score[1]); freopen("sticks.out", "w", stdout); pos = buffer; clr(buffer, 0); put_ll(k[1]); *pos = '\n'; *pos++; // sort(stapovi+1, stapovi+1+n, cmp_id); for(int i = 1; i <= k[1]; i++){ put_ll(rupa[1][i].size()); for(int j: rupa[1][i]) put_ll(j); // put_ll(stapovi[j].h); // put_ll(stapovi[j].p); *pos = '\n'; *pos++; } fwrite(buffer, 1, pos-buffer, stdout); } void calc_scre(int stp){ score[stp] = na3(k[stp]); for(int i = 1; i <= k[stp]; i++){ if(dubina[stp][i] > b){ score[stp] += stapovi[rupa[stp][i][rupa[stp][i].size()-1]].p; } } } void uporedi(){ if(score[0] < score[1]){ score[1] = score[0]; k[1] = k[0]; for(int i = 1; i <= k[0]; i++){ dubina[1][i] = dubina[0][i]; rupa[1][i].clear(); for(int j: rupa[0][i]) rupa[1][i].pb(j); } } } inline bool vredi_prebaciti(int id, int stp){ //id stare rupe return (na3(k[stp]+1) < na3(k[stp]) + stapovi[stare_rupe[id].indeks_stapa].p); //k^3+spi > (k+1)^3+spi-px } void optimizacija(bool q){ score[q] = k[q]*k[q]*k[q]; for(int i = 1; i <= k[q]; i++){ kolko_viri = dubina[q][i] - b; if(kolko_viri <= 0) continue; minimalni = inf; for(int j: rupa[q][i]){ if(stapovi[j].h > kolko_viri){ if(stapovi[j].p < minimalni){ minimalni = stapovi[j].p; indeks = j; } } } score[q] += minimalni; for(int j = 0; j < rupa[q][i].size(); j++){ if(indeks == rupa[q][i][j]){ swap(rupa[q][i][j], rupa[q][i][rupa[q][i].size()-1]); break; } } } } void obican(){ k[1] = 1; for(int i = 1; i <= n; i++){ if(dubina[1][k[1]] < b){ dubina[1][k[1]] += stapovi[i].h; rupa[1][k[1]].pb(i); } else{ k[1]++; i--; } } optimizacija(1); } struct N_manje_od_10{ void kombinatorna(int x){ int kraj = 1, id, indeks, staroq; bool ima; ll minimalni, kolko_viri; for(int i = 1; i <= n; i++) kraj *= x; for(int Q = 0; Q < kraj; Q++){ for(int i = 1; i <= x; i++){ rupa[0][i].clear(); dubina[0][i] = 0; } staroq = Q; for(int j = 1; j <= n; j++){ id = Q%x; rupa[0][id+1].pb(j); dubina[0][id+1] += stapovi[j].h; Q/=x; } Q = staroq; ima = 1; for(int i = 1; i <= x; i++){ if(dubina[0][i] == 0){ ima = 0; break; } } k[0] = x; if(!ima) continue; //neko je ostao prazan, to necu da radim optimizacija(0); uporedi(); } } void solve(){ for(int i = 2; i <= 5; i++) kombinatorna(i); if(score[1] == inf) obican(); } }n10; void prebaci_iz_u(int i1, int i2){ score[i2] = score[i1]; k[i2] = k[i1]; for(int i = 1; i <= k[i1]; i++){ dubina[i2][i] = dubina[i1][i]; rupa[i2][i].clear(); for(int j: rupa[i1][i]) rupa[i2][i].pb(j); } } bool algoritam(bool stp, int pola, bool radi=0){ while(pq_prostor.size()) pq_prostor.pop(); // deb(pola); for(int i = 1; i <= pola; i++){ rupa[stp][i].pb(stapovi[i].id); pq_prostor.push(make_pair(b-1, i)); } for(int i = pola+1; i <= n; i++){ if(pq_prostor.size() == 0) return 0; if(pq_prostor.top().first < stapovi[i].h) return 0; //nema dovoljno mesta za sve tren_top = pq_prostor.top(); pq_prostor.pop(); dubina[stp][tren_top.second] += stapovi[i].h; if(radi) rupa[stp][tren_top.second].pb(stapovi[i].id); tren_top.first -= stapovi[i].h; if(tren_top.first >= najmanji_h) pq_prostor.push(tren_top); } for(int i = 1; i <= pola; i++){ dubina[stp][i] += stapovi[i].h; if(radi) rupa[0][i].clear(); dubina[0][i] = 0; } k[stp] = pola; return 1; } void dodaj_novu(int id, int stp){ if(!vredi_prebaciti(id, stp)) return; spi = score[stp] - na3(k[stp]); ids = stare_rupe[id].indeks_stapa; score[stp] = spi - stapovi[ids].p + na3(k[stp]+1); k[stp]++; //ubacivanje u pq pomnr.indeks_rupe = k[stp]; pomnr.zauzeto = stapovi[ids].h; pq_rupa.push(pomnr); //updatovanje stare rupe rupa[stp][stare_rupe[id].indeks_rupe].pop_back(); dubina[stp][stare_rupe[id].indeks_rupe] -= stapovi[ids].h; //updatovanje nove rupe rupa[stp][k[stp]].pb(ids); dubina[stp][k[stp]] += stapovi[ids].h; //dodavanje stare rupe kao nove pomnr.indeks_rupe = stare_rupe[id].indeks_rupe; pomnr.zauzeto = dubina[stp][pomnr.indeks_rupe]; pq_rupa.push(pomnr); } void prebaci(int id, int stp){ int ids = stare_rupe[id].indeks_stapa; score[stp] -= stapovi[ids].p; //ubacivanje u pq pomnr = pq_rupa.top(); pq_rupa.pop(); pomnr.zauzeto += stapovi[ids].h; //updatujem samo zauzeto pq_rupa.push(pomnr); //updatovanje stare rupe rupa[stp][stare_rupe[id].indeks_rupe].pop_back(); dubina[stp][stare_rupe[id].indeks_rupe] -= stapovi[ids].h; //updatovanje nove rupe rupa[stp][pomnr.indeks_rupe].pb(ids); dubina[stp][pomnr.indeks_rupe] += stapovi[ids].h; //dodavanje rupe iz koje sam prebacio kao novu rupu pomnr.indeks_rupe = stare_rupe[id].indeks_rupe; pomnr.zauzeto = dubina[stp][pomnr.indeks_rupe]; pq_rupa.push(pomnr); } void optimizacija_penaltija(int stp){ int id; nstare = 0; for(int i = 1; i <= k[stp]; i++){ if(rupa[stp][i].size() == 0) continue; id = rupa[stp][i][rupa[stp][i].size()-1]; if(dubina[stp][i] > b){ nstare++; stare_rupe[nstare].indeks_rupe = i; stare_rupe[nstare].indeks_stapa = stapovi[id].id; stare_rupe[nstare].penalti = stapovi[id].p; } } sort(stare_rupe+1, stare_rupe+1+nstare, cmp_sr_penalty); // cout << "Sortirao sam\n"; for(int i = 1; i <= nstare; i++){ if(stapovi[stare_rupe[i].indeks_stapa].h > b) continue; //nema poente prebacivati ga if(pq_rupa.size() == 0) //nema dostupnih dodaj_novu(i, stp); else if(b - pq_rupa.top().zauzeto >= stapovi[stare_rupe[i].indeks_stapa].h) //moze da udje u neki postojecu novu rupu prebaci(i, stp); else dodaj_novu(i, stp); //moram pravit novu } } void binarna(){ sort(stapovi+1, stapovi+1+n, cmp_stapovi_h_plus_p); int l, r, mid, uspeo, ko_moze; l = 1; r = n; while(l <= r){ mid = (l+r)/2; uspeo = algoritam(0, mid); if(uspeo){ r = mid-1; ko_moze = mid; } else l = mid+1; } // deb(ko_moze); uspeo = algoritam(1, ko_moze, 1); calc_scre(1); // for(int i = 1; i <= k[1]; i++) cout << rupa[1][i].size() << endl; // deb(score[0]); // deb(score[1]); sort(stapovi+1, stapovi+1+n, cmp_id); optimizacija(1); calc_scre(1); // optimizacija_penaltija(1); uporedi(); // for(int i = 1; i <= k[1]; i++) cout << rupa[1][i].size() << endl; } void optimizacija_zameni_dva_podudarna(int stp){ ///OVDE NASTAJU PROBLEMI VELIKI, TREBA GLEDAT ONE SLUCAJEVE KAD VIRI A KAD MU UTERA int x, Q, kraj, uradio = 0, z, zadnji; for(int i = 1; i <= k[stp]; i++){ if(dubina[stp][i] <= b) continue; //gledam samo one vrhove koji su preko B for(int j = 1; j <= k[stp]; j++){ if(j == i) continue; kraj = rupa[stp][j].size(); for(int idz = 0; idz < kraj; idz++){ x = rupa[stp][i][rupa[stp][i].size()-1]; //x je indeks zadnjeg z = rupa[stp][j][idz]; //z je indeks nekog koga menjam delta_score = 0; if(dubina[stp][i] > b) delta_score -= stapovi[x].p; if(dubina[stp][j] > b) delta_score -= stapovi[rupa[stp][j][kraj-1]].p; dubi = dubina[stp][i]-stapovi[x].h+stapovi[z].h; dubj = dubina[stp][j]+stapovi[x].h-stapovi[z].h; if(idz == kraj-1) zadnji = x; else zadnji = rupa[stp][j][kraj-1]; if(dubi - stapovi[z].h >= b or dubj - stapovi[zadnji].h >= b) continue; if(dubi > b) delta_score += stapovi[z].p; if(dubj > b) delta_score += stapovi[zadnji].p; if(delta_score < 0){ // return; score[stp] += delta_score; //score dubina[stp][i] += stapovi[z].h - stapovi[x].h; //dubine dubina[stp][j] += stapovi[x].h - stapovi[z].h; Q = z; //fizicki deo rupa[stp][j].erase(rupa[stp][j].begin()+idz); // brisem z iz j rupa[stp][i].pop_back(); // popujem sa i tako skidam zadnji sa i rupa[stp][i].push_back(Q); // i-u pushujem Q, a to je z Q = rupa[stp][j][rupa[stp][j].size()-1]; // Q je zadnji na j if(idz != kraj-1) // ako z nije poslednji rupa[stp][j].pop_back(); // skidam zadnjeg sa j rupa[stp][j].push_back(x); // pusham x na j if(idz != kraj-1) // ako z nije poslednji rupa[stp][j].push_back(Q); // pusham zadnjeg sa j nazad na j // return; } } // if(uradio == 1) break; } } } void otvori_novu_rupu(){ // calc_scre(1); prebaci_iz_u(1, 0); k[1]++; dubina[1][k[1]] = 0; rupa[1][k[1]].clear(); // cout << "zapocnjem\n"; optimizacija_penaltija(1); calc_scre(1); // deb(score[1]); // deb(score[0]); if(score[1] > score[0]) prebaci_iz_u(0, 1); } bool algoritam_optimizacije(int poc_rupa, ll &nabacivanje, bool radi = 0){ ll kolko_sam_imo; int id_it; nabacivanje = 0; for(int j = 0; j < rupa[0][poc_rupa].size(); j++){ it = set_rupa.upper_bound(make_pair(stapovi[rupa[0][poc_rupa][j]].h, 0)); if(it == set_rupa.end()){ while(qju.size()){ if(-qju.top().first != b-nove_dubine[qju.top().second]) qju.pop(); else break; } if(qju.size() == 0) return 0; par = qju.top(); it = set_rupa.find(make_pair(b-nove_dubine[par.second], par.second)); set_rupa.erase(it); nove_dubine[par.second] += stapovi[rupa[0][poc_rupa][j]].h; if(radi){ dubina[0][par.second] += stapovi[rupa[0][poc_rupa][j]].h; // cout << par.second << " += " << stapovi[rupa[0][poc_rupa][j]].h << endl; rupa[0][par.second].pb(stapovi[rupa[0][poc_rupa][j]].id); } qju.pop(); nabacivanje += stapovi[rupa[0][poc_rupa][j]].p; } else{ id_it = (*it).second; kolko_sam_imo = (*it).first; nove_dubine[id_it] += stapovi[rupa[0][poc_rupa][j]].h; if(nove_dubine[id_it] != 0) qju.push(make_pair(-b+nove_dubine[id_it], id_it)); if(radi){ dubina[0][id_it] += stapovi[rupa[0][poc_rupa][j]].h; // cout << id_it << " += " << stapovi[rupa[0][poc_rupa][j]].h << endl; rupa[0][id_it].pb(stapovi[rupa[0][poc_rupa][j]].id); } set_rupa.erase(it); set_rupa.insert(make_pair(kolko_sam_imo - stapovi[rupa[0][poc_rupa][j]].h, id_it)); } } if(radi){ // deb(poc_rupa); swap(dubina[0][k[0]], dubina[0][poc_rupa]); swap(rupa[0][k[0]], rupa[0][poc_rupa]); k[0]--; calc_scre(0); // deb(score[0]); } return 1; } void priprema_algoritma_prebacivanja(int poc_rupa){ set_rupa.clear(); while(qju.size()) qju.pop(); for(int i = 1; i <= k[0]; i++){ if(i != poc_rupa){ set_rupa.insert(make_pair(b-dubina[0][i], i)); if(-b+dubina[0][i] < 0) qju.push(make_pair(-b+dubina[0][i], i)); } nove_dubine[i] = dubina[0][i]; } } void algoritam_slaganje_po_velicini(){ sort(stapovi+1, stapovi+1+n, cmp_stapovi_h_veci); k[0] = score[0] = 0; for(int i = 1; i <= n; i++) rupa[0][i].clear(); int id_it, kolko_sam_imo, uspeo; for(int i = 1; i <= n; i++){ if(stapovi[i].h >= b){ rupa[0][++k[0]].pb(stapovi[i].id); dubina[0][k[0]] = stapovi[i].h; } else{ // ovo je bitno if(set_rupa.size() == 0){ rupa[0][++k[0]].pb(stapovi[i].id); set_rupa.insert(make_pair(b-stapovi[i].h, k[0])); dubina[0][k[0]] = stapovi[i].h; } else{ it = set_rupa.upper_bound(make_pair(stapovi[i].h, 0)); if(it == set_rupa.end()){ rupa[0][++k[0]].pb(stapovi[i].id); set_rupa.insert(make_pair(b-stapovi[i].h, k[0])); dubina[0][k[0]] = stapovi[i].h; } else{ id_it = (*it).second; rupa[0][id_it].pb(stapovi[i].id); dubina[0][id_it] += stapovi[i].h; set_rupa.erase(it); set_rupa.insert(make_pair(b - dubina[0][id_it], id_it)); } } } } sort(stapovi+1, stapovi+1+n, cmp_id); calc_scre(0); ll nabacivanje, min_nabacivanje = inf, best_poc_rupa; while(true){ min_nabacivanje = inf; uspeo = 0; for(int poc_rupa = 1; poc_rupa <= k[0]; poc_rupa++){ priprema_algoritma_prebacivanja(poc_rupa); if(algoritam_optimizacije(poc_rupa, nabacivanje)){ if(nabacivanje < min_nabacivanje){ uspeo = 1; min_nabacivanje = nabacivanje; best_poc_rupa = poc_rupa; } } } if(!uspeo or (score[0] < score[0] + min_nabacivanje - na3(k[0]) + na3(k[0]-1))) break; //ovo znaci da li uopste moze da se prebaci priprema_algoritma_prebacivanja(best_poc_rupa); uspeo = algoritam_optimizacije(best_poc_rupa, min_nabacivanje, 1); // break; } optimizacija_penaltija(0); calc_scre(0); uporedi(); } int main(){ unos(); if(n <= 10) n10.solve(); else binarna(); if(k[1]*n <= 1000000){ optimizacija_zameni_dva_podudarna(1); optimizacija_penaltija(1); } // deb(score[1]); if(n <= 1000) algoritam_slaganje_po_velicini(); otvori_novu_rupu(); for(int i = 1; i <= 10 and n <= 1e4; i++) optimizacija_zameni_dva_podudarna(1); otvori_novu_rupu(); ispis(); return 0; }