#include #define lastStick(solution, holeIdx) solution.holes[holeIdx].sticks[solution.holes[holeIdx].sticks.size()-1] using namespace std; using namespace std::chrono; int n, k;//, scores[15]; long long b; struct stick { int h=0; int idx=0; long long p=0; }; namespace Gen { const int POPULATION_SIZE = 100; const int GENERATIONS = 1000; const float MUTATION_RATE = 0.2; const float MUTATION_WIDTH = 0.1; const float ELITISM_RATE = 0.1; float TIME_LIMIT = 4; float MICROSECONDS_LIMIT = TIME_LIMIT * 1000000; int elitismSize = (int)round(ELITISM_RATE*POPULATION_SIZE); stick allSticks[1000005]; bool cmpHeight(stick& a, stick& b) { return a.h < b.h; } int myrandom (int i) { return rand()%i;} struct hole { vector sticks; long long totalHeight = 0; void AddStick(stick* st) { sticks.push_back(st); totalHeight += st->h; } void RemoveLastStick() { totalHeight -= sticks[sticks.size()-1]->h; sticks.pop_back(); } void RemoveStick(int idx) { totalHeight -= sticks[idx]->h; int sticksSize = sticks.size(); if (idx < sticksSize-2) { swap(sticks[idx],sticks[sticksSize-2]); swap(sticks[sticksSize-2],sticks[sticksSize-1]); sticks.pop_back(); } else { sticks.erase(sticks.begin()+idx); } } void AddStickNotEnd(stick* st) { sticks.push_back(st); if (sticks.size() > 1) swap(sticks[sticks.size()-2], sticks[sticks.size()-1]); totalHeight += st->h; } }; hole holes[1000005]; struct Solution { vector holes; long long score; //map stickToHole; }; Solution population[POPULATION_SIZE+15], parents1[POPULATION_SIZE/2+15], parents2[POPULATION_SIZE/2+15], children[POPULATION_SIZE+15]; void printHoles(vector holes); long long GradeSolution(vector& holes, int k = 0) { long long score = 0; int emptyHoles = 0; k = holes.size(); for (int i=0;i b) score += holes[i].sticks[holes[i].sticks.size()-1]->p; else if (holes[i].totalHeight == 0) emptyHoles++; } score += (k-emptyHoles)*(k-emptyHoles)*(k-emptyHoles); return score; } int indexes[1000005]; void FitSticksNoOverflow(Solution& sol){ int k = 0; sol.holes.emplace_back(); for(int i=1;i<=n;i++) { if (allSticks[indexes[i]].h > b) { if (sol.holes[k].totalHeight > 0) { k++; sol.holes.emplace_back(); } sol.holes[k].AddStick(&allSticks[indexes[i]]); //sol.stickToHole[sticks[i].idx] = &sol.holes[k]; } else if (sol.holes[k].totalHeight + allSticks[indexes[i]].h <= b) { sol.holes[k].AddStick(&allSticks[indexes[i]]); //sol.stickToHole[sticks[i].idx] = &sol.holes[k]; } else { k++; sol.holes.emplace_back(); i--; } } //return k; } void GeneratePopulation() { //sort(sticks+1, sticks+n+1, cmpHeight); for (int i=1;i<=n;i++) indexes[i] = i; for (int i=1;i<=POPULATION_SIZE;i++) { random_shuffle(indexes+1, indexes+n+1, myrandom); /*for (int s=1;s<=n;s++) { cout<<"("<idx] = &sol.holes[newHoleIdx]; sol.holes[newHoleIdx].AddStick(sol.holes[holeIdx].sticks[stickIdx]); sol.holes[holeIdx].RemoveStick(stickIdx); } //cout<<"- uspeo\n"; } toMutate = rand()%(int)ceil(MUTATION_WIDTH*n); /// Swap if (rand()%1000 < MUTATION_RATE*1000) { //cout<<"Mutiram swap "; for (int i=1; i<=toMutate; i++) { int holeAIdx = rand()%sol.holes.size(); while (sol.holes[holeAIdx].totalHeight == 0) holeAIdx = rand()%sol.holes.size(); int stickAIdx = rand()%sol.holes[holeAIdx].sticks.size(); int holeBIdx = rand()%sol.holes.size(); while (sol.holes[holeBIdx].totalHeight == 0) holeBIdx = rand()%sol.holes.size(); int stickBIdx = rand()%sol.holes[holeBIdx].sticks.size(); if (holeAIdx == holeBIdx) continue; stick* stickA = sol.holes[holeAIdx].sticks[stickAIdx]; stick* stickB = sol.holes[holeBIdx].sticks[stickBIdx]; if (sol.holes[holeAIdx].totalHeight - stickA->h >= b) return; if (sol.holes[holeBIdx].totalHeight - stickB->h >= b) return; sol.holes[holeAIdx].RemoveStick(stickAIdx); sol.holes[holeBIdx].RemoveStick(stickBIdx); sol.holes[holeBIdx].AddStick(stickA); sol.holes[holeAIdx].AddStick(stickB); //sol.stickToHole[stickA->idx] = &sol.holes[holeBIdx]; //sol.stickToHole[stickB->idx] = &sol.holes[holeAIdx]; } //cout<<"- uspeo\n"; } toMutate = rand()%(int)ceil(MUTATION_WIDTH*n); /// Shuffle if (rand()%1000 < MUTATION_RATE*1000) { //cout<<"Mutiram shuffle "; for (int i=1; i<=toMutate; i++) { int holeIdx = rand()%sol.holes.size(); while (sol.holes[holeIdx].totalHeight == 0) holeIdx = rand()%sol.holes.size(); random_shuffle(sol.holes[holeIdx].sticks.begin(), sol.holes[holeIdx].sticks.end(), myrandom); int targetHeight = sol.holes[holeIdx].totalHeight - b + 1; int sticksSize = sol.holes[holeIdx].sticks.size(); if (sol.holes[holeIdx].sticks[sticksSize-1]->h < targetHeight) { for (int j=0;jh >= targetHeight) { swap(sol.holes[holeIdx].sticks[j], sol.holes[holeIdx].sticks[sticksSize-1]); break; } } } } //cout<<"- uspeo\n"; } } void Crossover() { for (int p=1;p<=POPULATION_SIZE/2;p++) { children[p*2-1].holes = parents1[p].holes; children[p*2].holes = parents2[p].holes; int toSwap = n/2; while (toSwap--) { //cout<<"child1\n"; //printHoles(children[p*2-1].holes); //cout<<"child2\n"; //printHoles(children[p*2].holes); int oldHole1Idx = rand()%children[p*2-1].holes.size(); //cout<= children[p*2].holes.size()) children[p*2].holes.emplace_back(); while(oldHole2Idx >= children[p*2-1].holes.size()) children[p*2-1].holes.emplace_back(); if (children[p*2-1].holes[oldHole2Idx].totalHeight >= b) continue; if (children[p*2-1].holes[oldHole2Idx].totalHeight != 0 && children[p*2-1].holes[oldHole2Idx].totalHeight - lastStick(children[p*2-1], oldHole2Idx)->h + stickk->h >= b) continue; if (children[p*2].holes[oldHole1Idx].totalHeight >= b) continue; if (children[p*2].holes[oldHole1Idx].totalHeight != 0 && children[p*2].holes[oldHole1Idx].totalHeight - lastStick(children[p*2], oldHole1Idx)->h + stickk->h >= b) continue; children[p*2-1].holes[oldHole1Idx].RemoveStick(stick1Idx); //cout<<">"; children[p*2].holes[oldHole2Idx].RemoveStick(stick2Idx); children[p*2-1].holes[oldHole2Idx].AddStickNotEnd(stickk); children[p*2].holes[oldHole1Idx].AddStickNotEnd(stickk); } } } long long scores[POPULATION_SIZE+15], weights[POPULATION_SIZE+15]; void RouletteSelection() { for (int i=1;i<=POPULATION_SIZE;i++) population[i].score = GradeSolution(population[i].holes); for (int i=1;i<=POPULATION_SIZE/2;i++) { long long bestScore=4e18, secondScore=4e18; int bestIdx = 0, secondIdx = 0; for (int j=1;j<=POPULATION_SIZE;j++) weights[j] = (double)population[j].score * ((rand()%10000)/10000.0); for (int j=1;j<=POPULATION_SIZE;j++) if (weights[j] <= bestScore) { bestScore = weights[j]; bestIdx = j; } for (int j=1;j<=POPULATION_SIZE;j++) { if (j == bestIdx) continue; if (weights[j] <= secondScore) { secondScore = weights[j]; secondIdx = j; } } //cout<<" B:"< holes) { int i=0; for (hole& h:holes) { cout<<" Hole "<h<<","<idx<<","<p<<") "; } cout<p; for (int j=0;jh >= minimalHeight && h.sticks[j]->p < bestP) { bestP = h.sticks[j]->p; bestStick = j; } } swap(h.sticks[bestStick], h.sticks[h.sticks.size()-1]); } } cout<idx<<" "; //cout<<"("<>Gen::allSticks[i].h; Gen::allSticks[i].idx = i; } for (int i=1;i<=n;++i) { cin>>Gen::allSticks[i].p; } srand(10); auto start = high_resolution_clock::now(); Gen::GeneratePopulation(); for (int g=1;g<=Gen::GENERATIONS;g++) { Gen::RouletteSelection(); /// sets parents1 and parents2 Gen::Crossover(); /// sets children from parent1 and parents2 auto duration = duration_cast(high_resolution_clock::now() - start); if (duration.count() > Gen::MICROSECONDS_LIMIT) { break; } for (int i=1;i<=Gen::POPULATION_SIZE;i++) Gen::MutateSol(Gen::children[i]); /// mutates children Gen::Elitism(); /// creates new population from old one and children duration = duration_cast(high_resolution_clock::now() - start); if (duration.count() > Gen::MICROSECONDS_LIMIT) { break; } } Gen::findAndPrintBest(); } } namespace Norm { int compares = 2; int solutions = 4; stick sticks[1000005]; struct hole { vector sticks; int totalHeight; void AddStick(stick& stick) { sticks.push_back(stick); totalHeight += stick.h; } }; bool cmpHeight(stick& a, stick& b) { return a.h < b.h; } bool cmpHeightReverse(stick& a, stick& b) { return a.h > b.h; } bool cmpIdx(stick& a, stick& b) { return a.idx < b.idx; } function cmps[105]; long long scores[105]; hole holes[1000005]; int FitSticksNoOverflow(hole* holes){ int k = 1; for(int i=1;i<=n;i++) { if (sticks[i].h > b) { if (holes[k].totalHeight > 0) k++; holes[k].AddStick(sticks[i]); } else if (holes[k].totalHeight + sticks[i].h <= b) { holes[k].AddStick(sticks[i]); } else { k++; i--; } } return k; } int FitSticksOverflow(hole* holes){ int k = 1; for(int i=1;i<=n;i++) { if (holes[k].totalHeight >= b) k++; /*if (sticks[i].h > b) { if (holes[k].totalHeight > 0) k++; holes[k].AddStick(sticks[i]); }*/ //if (holes[k].totalHeight + sticks[i].h <= b) //{ holes[k].AddStick(sticks[i]); //} /*else { k++; i--; }*/ } return k; } /*int FitSticksExactSum(hole* holes){ int k = 1; bool success; bool added[1000005]; memset(added, false, sizeof(added)); for (int i=1;i<=n;i++) { if (i>1 && holes[k].totalHeight + sticks[i].h > b) k++; holes[k].AddStick(sticks[i]); success = false; for (int j=i+1;j<=n;j++) { if (added[j]) continue; if (holes[k].totalHeight + sticks[j].h == b) { holes[k].AddStick(sticks[j]); added[j] = true; k++; success = true; break; } } //if (success) // continue; } return k; }*/ long long GradeSolution(hole* holes, int k){ long long score = 0; for (int i=1;i<=k;i++) { if (holes[i].totalHeight > b) score += holes[i].sticks[holes[i].sticks.size()-1].p; } score += k*k*k; return score; } void ClearHoles(hole* holes, int k){ for (int i=1;i<=k;i++) { holes[i].sticks.clear(); holes[i].totalHeight = 0; } } void MainPart() { cmps[0] = &cmpHeight; cmps[1] = &cmpHeightReverse; for (int i=1;i<=n;++i) { cin>>sticks[i].h; sticks[i].idx = i; } for (int i=1;i<=n;++i) { cin>>sticks[i].p; } //if (n>10000) for (int i=0;i= minimalHeight && holes[i].sticks[j].p < bestP) { bestP = holes[i].sticks[j].p; bestStick = j; } } swap(holes[i].sticks[bestStick], holes[i].sticks[holes[i].sticks.size()-1]); } //cout<>n>>b; if (n<=100) { Gen::MainPart(); } else { Norm::MainPart(); } return 0; }