#include using namespace std; long long int n,b,p[1000005],h[1000007],res,k,broj; vector < long long int> v[1000005]; vector < long long int> indeks[1000005]; long long int penali; long long int br,a[1000005],brojac,brindex; int brrr[1000005]; long long int brx,x[100005],br1,br2,as[100005]; long long int ct,counter,sol,brojacbrojaca,brojacc,counterr,brrojac,brojanac,brmax,c[100005],ha[100005]; map brr; struct slog{ long long int index; long long int velicina; long long int penalty; }; slog pu[1000005]; bool cmp(slog x, slog y){ if(abs(x.velicina-y.velicina)<=round(0.101*(x.velicina+y.velicina))){ return x.penalty>y.penalty; } return x.velicina> n; cin >> b; for(int i=1;i<=n;i++){ cin >> h[i]; } for(int i=1;i<=n;i++){ cin >> p[i]; } } void obrada(){ for(int i=1;i<=n;i++){ pu[i].velicina=h[i]; pu[i].index=i; pu[i].penalty=p[i]; } sort(pu+1,pu+n+1,cmp); k=1; int maximum=n; int prebroj; int L=1; int R=n; for(int i=1;i<=n;i++){ res+=pu[i].velicina; if(res<=b and R>=L){ v[k].push_back(pu[i].velicina); L++; indeks[k].push_back(pu[i].index); if(res==b){ res=0; k++; } } if(res>b and R>=L){ v[k].push_back(pu[maximum].velicina); R--; indeks[k].push_back(pu[maximum].index); maximum--; res=0; if(R>=L){ k++; v[k].push_back(pu[i].velicina); L++; indeks[k].push_back(pu[i].index); res=pu[i].velicina; if(res>b){ res=0; k++; } } } } } void obrada1(){ for(int i=1;i<=n;i++){ pu[i].velicina=h[i]; pu[i].index=i; } sort(pu+1,pu+n+1,cmp); sort(h+1, h + n+1); //for(int i=1;i<=n;i++){ // cout << h[i] << " "; //} for(int i=1;i<=n+1;i++){ if(i<=n){ res=res+h[i]; } br++; if(br!=0 and res>b or br!=0 and resn ){ k++; res=h[i]; br--; brrr[i]=br; br=1; } } brindex=1; cout << k << endl; for (map::iterator it=brr.begin(); it!= brr.end(); ++it){ cout << it->second << " "; for(int i=1;i<=it->second;i++){ cout << pu[brindex].index << " "; brindex++; } cout << endl; } } void obrada2(){ brindex=1; for(int i=1;i<=n;i++){ if(b>res){ res=res+h[i]; br++; //cout << "Res: " << res << " Broj Stapova: " << br; } if(resb){ brrr[i]=br; res=0; br=0; k++; } //cout << " Ovo je br stapova: "<< brr[i]; } cout << k << endl; for(int i=1;i<=n;i++){ if(brrr[i]!=0) { cout << brrr[i] << " "; //brojac++; //} //cout << " Ovo je Brojac: " << brojac << " Ovo je i: "<=L){ v[k].push_back(pu[i].velicina); L++; indeks[k].push_back(pu[i].index); if(res==b){ res=0; k++; } } if(res>b and R>=L){ if(p[i]<=100){ v[k].push_back(pu[maximum].velicina); R--; indeks[k].push_back(pu[maximum].index); maximum--; res=0; if(R>=L){ k++; v[k].push_back(pu[i].velicina); L++; indeks[k].push_back(pu[i].index); res=pu[i].velicina; if(res>b){ res=0; k++; } } } if(p[i]>=100){ k++; v[k].push_back(pu[i].velicina); L++; indeks[k].push_back(pu[i].index); res=pu[i].velicina; } } } } //brl=L; //brr=R; // // if(v[i].size()==2 and ct==1){ // // sort(pu+1,pu+n+1,cmp1); // ct++; // } // if(i!=k){ // // // if(pu[i].velicina=b and indeks[i][R]=b){ // indeks[i].push_back(pu[R].index); // res[k]+=pu[R].velicina; // R--; // k++; // indeks[i].push_back(pu[L].index); // res[k]+=pu[L].velicina; // L++; // } // if(indeks[i][L]>=b and indeks[i][R]>=b){ // indeks[i].push_back(pu[R].index); // res[k]+=pu[R].velicina; // R--; // k++; // indeks[i].push_back(pu[L].index); // res[k]+=pu[L].velicina; // L++; // k++; // } // //} //} //z=k; //} // void penmaxing(){ // // for(int i=k;i>=k/2;i--){ // if(indeks[i].size()>1){ // //if(pu[indeks[z].back()].penalty!=0 and pu[indeks[i].front()].penalty!=0){ // //if(pu[indeks[z].back()].penalty>pu[indeks[i].front()].penalty){ // //swap(indeks[z].back(),indeks[i].front()); // //z--; // } // } //} // } // } //void provera(){ // int brojacIndexa; // int finalni; // int h; // int duzinav; // int finalidx; // for(int i=1;i<=k;i++){ // //cout << " a "; // if(res[i]>b){ //cout << " OVO JE resenje: " << res[i]; //cout << " Ovo je minheight " << h; // for(int j=0;jb)score+=pu[indeks[i][vrh]].penalty; // } // for(int i=k;i>=1;i--){ // minscore=(k+1)*(k+1)*(k+1)-pu[indeks[i][vrh]].penalty; // if(minscore=L){ // v[k].push_back(pu[i].velicina); // L++; // indeks[k].push_back(pu[i].index); // if(res[k]==b){ // res[k]=0; // k++; // } // // } // if(res[k]>b and R>=L){ // if(p[i]<=100){ // v[k].push_back(pu[maximum].velicina); // R--; // indeks[k].push_back(pu[maximum].index); // maximum--; // res[k]=0; // if(R>=L){ // k++; // v[k].push_back(pu[i].velicina); // L++; // indeks[k].push_back(pu[i].index); // // res[k]=pu[i].velicina; // if(res[k]>b){ // res[k]=0; // k++; // } // // } // } // if(p[i]>=100){ // k++; // v[k].push_back(pu[i].velicina); // L++; // indeks[k].push_back(pu[i].index); // res[k]=pu[i].velicina; // } // // } // // // // } // } void penal(){ for(int i=1;i<=k;i++){ penali+=pu[i].penalty; } } void izlaz(){ broj=0; cout << k << endl; for(int j=1;j<=k;j++){ cout << v[j].size()<< " "; for(int i=0;i500)obrada3(); else obrada(); izlaz(); return 0; }