Submission #1192158

#TimeUsernameProblemLanguageResultExecution timeMemory
1192158burgerguyRobots (IOI13_robots)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> #include "robots.h" using namespace std; using ll = long long; struct Toy { ll weight, size, index; }; bool cmpWeight(Toy& a, Toy& b) { if(a.weight == b.weight) return a.size > b.size; return a.weight < b.weight; } bool cmpSize(Toy& a, Toy& b){ if(a.size == b.size) return a.weight > b.weight; return a.size > b.size; } ll toyCount; vector<ll> robotWeights, robotSizes; vector<Toy> toyWeights, toySizes; bool isValidTime(ll time) { vector<bool> completedToys(toyCount); priority_queue<pair<ll,ll>> pq; ll curToyIndex = 0; for (int curRobot = 0; curRobot < robotWeights.size(); ++curRobot) { ll curWeightLimit = robotWeights[curRobot]; while(curToyIndex < toyCount) { Toy& curToy = toyWeights[curToyIndex]; if(curToy.weight >= curWeightLimit) break; if(completedToys[curToy.index]) continue; pq.emplace(curToy.size, curToy.index); ++curToyIndex; } ll toysPickedUp = 0; while(!pq.empty() && toysPickedUp < time) { ll curToyIndex = pq.top().second; pq.pop(); if(completedToys[curToyIndex]) continue; ++toysPickedUp; completedToys[curToyIndex] = true; } } curToyIndex = 0; for (int curRobot = 0; curRobot < robotSizes.size(); ++curRobot) { ll curSizeLimit = robotSizes[curRobot]; ll toysPickedUp = 0; while(curToyIndex < toyCount) { Toy& curToy = toyWeights[curToyIndex]; if(completedToys[curToy.index]) { ++curToyIndex; continue; } if(toysPickedUp == time) break; if(curToy.size >= curSizeLimit) return false; ++toysPickedUp; ++curToyIndex; } } return true; } int putaway(int A,int B,int T, int X[],int Y[],int W[],int S[]) { toyCount = T; for (int i = 0; i < A; ++i) { robotWeights.push_back(X[i]); } for (int i = 0; i < B; ++i) { robotSizes.push_back(Y[i]); } for (int i = 0; i < T; ++i) { toyWeights.push_back({W[i], S[i], i}); } sort(toyWeights.begin(), toyWeights.end(), cmpWeight); sort(toySizes.begin(), toySizes.end(), cmpSize); sort(robotWeights.begin(), robotWeights.end()); sort(robotSizes.rbegin(), robotSizes.rend()); ll minTime = 1, maxTime = T; while(minTime <= maxTime) { ll midTime = (maxTime + minTime)/2; if(isValidTime(midTime)) { maxTime = midTime - 1; } else { minTime = midTime + 1; } } if(isValidTime(minTime)) return minTime; else return -1; } //int main() { // ll A,B,T; cin >> A >> B >> T; // int X[A], Y[B], W[T], S[T]; // // for (int i = 0; i < A; ++i) { // cin >> X[i]; // } // for (int i = 0; i < B; ++i) { // cin >> Y[i]; // } // // for (int i = 0; i < T; ++i) { // cin >> W[i] >> S[i]; // } // // cout << putaway(A,B,T,X,Y,W,S) << '\n'; //}
#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...