Submission #1192340

#TimeUsernameProblemLanguageResultExecution timeMemory
1192340TroySerRobots (IOI13_robots)C++20
100 / 100
1762 ms24940 KiB
#include <bits/stdc++.h> #include "robots.h" using namespace std; using ll = int; struct Toy { ll ind; ll weight; ll sz; }; bool cmpForWeight(const Toy &a, const Toy &b) { return a.weight < b.weight; } bool cmpForSize(const Toy &a, const Toy &b) { return a.sz < b.sz; } vector<ll> weakRobots, smallRobots; vector<Toy> considerWeak, considerSmall; ll t, a, b; vector<bool> taken; bool check(ll atMostTime) { priority_queue<pair<ll, ll> > pq; taken.clear(); taken.resize(t, false); ll toyRemaining = t; ll ind = 0; for (ll i = 0; i < a; i++) { // for EACH weak robot, keep taking up to `atMostTime` number of toys while (ind < t && (taken[considerWeak[ind].ind] || considerWeak[ind].weight < weakRobots[i])) { if (!taken[considerWeak[ind].ind]) { pq.push({considerWeak[ind].sz, considerWeak[ind].ind}); } ind++; } // can take at most `atMostTime` toys, and deduct 1 toy from the entire collection ll timeRemaining = atMostTime; while (!pq.empty() && timeRemaining > 0) { ll currInd = pq.top().second; pq.pop(); timeRemaining--; toyRemaining--; taken[currInd] = true; } } pq = priority_queue<pair<ll, ll> >(); ind = 0; for (ll i = 0; i < b; i++) { // for EACH small robot, keep taking up to `atMostTime` number of toys // ofc take toys as needed, if you took it then no need while (ind < t && (taken[considerSmall[ind].ind] || considerSmall[ind].sz < smallRobots[i])) { if (!taken[considerSmall[ind].ind]) { pq.push({considerSmall[ind].weight, considerSmall[ind].ind}); } ind++; } ll timeRemaining = atMostTime; while (!pq.empty() && timeRemaining > 0) { ll currInd = pq.top().second; pq.pop(); timeRemaining--; toyRemaining--; taken[currInd] = true; } } return (toyRemaining == 0); } int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { t = T; a = A; b = B; weakRobots.resize(A); for (ll i = 0; i < A; i++) { weakRobots[i] = X[i]; } smallRobots.resize(B); for (ll i = 0; i < B; i++) { smallRobots[i] = Y[i]; } // sort from worst ==> best robot, we can show na letting worst // robot take the easiest load is always optimal sort(weakRobots.begin(), weakRobots.end()); sort(smallRobots.begin(), smallRobots.end()); considerWeak.resize(T); considerSmall.resize(T); for (ll i = 0; i < T; i++) { considerWeak[i] = Toy{i, W[i], S[i]}; considerSmall[i] = Toy{i, W[i], S[i]}; } // same logic as above but focusing on toys sort(considerWeak.begin(), considerWeak.end(), cmpForWeight); sort(considerSmall.begin(), considerSmall.end(), cmpForSize); ll l = 0, r = T + 1; while (l < r) { ll M = (l + r) / 2; if (check(M)) { r = M; } else { l = M + 1; } } return (check(l) ? l : -1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...