Submission #1189552

#TimeUsernameProblemLanguageResultExecution timeMemory
1189552spacewalkerRobots (IOI13_robots)C++20
28 / 100
160 ms16640 KiB
#include "robots.h" #include <bits/stdc++.h> using namespace std; namespace r = ranges; namespace v = ranges::views; template <typename R> vector<r::range_value_t<R>> vec_of(R &&range) { return vector(range.begin(), range.end()); } bool can_put_away(const vector<int> &layers, int A, int B, int toys_per_bot) { long long pending = 0, ctoy = 0; for (int clayer = 0; clayer <= max(A, B); ++clayer) { while (ctoy < layers.size() && layers[ctoy] <= clayer) { ++pending; ++ctoy; } // how many bots can we clear at this layer? // at layer 0, there are no bots // at layer 1...min(A, B), we have one horizontal and one vertical bot // at all other layers we only have one other bot int clearable = (clayer == 0 ? 0 : (clayer <= min(A, B) ? 2 * toys_per_bot : toys_per_bot)); // allow pending to go negative, to allow bots here to put away bots we discover later on pending -= clearable; if (pending > 0) return false; } return true; } int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { vector<int> weight_limits(X, X + A); vector<int> size_limits(Y, Y + B); r::sort(weight_limits); r::sort(size_limits); // where is my ranges::to bwaaaaaaaaa vector<pair<int, int>> toys = vec_of( v::iota(0, T) | v::transform([&](int i) { return pair{W[i], S[i]}; })); vector<pair<int, int>> compressed_toys = vec_of( toys | v::transform([&](pair<int, int> p) { return pair{(int)distance(weight_limits.begin(), r::upper_bound(weight_limits, p.first)), (int)distance(size_limits.begin(), r::upper_bound(size_limits, p.second))}; })); vector<int> layers = vec_of(compressed_toys | v::transform([&](pair<int, int> p) { return max(A - p.first, B - p.second); })); r::sort(layers); if (!can_put_away(layers, A, B, T)) return -1; int lo = 1, hi = T; while (lo < hi) { int mid = (lo + hi) / 2; /*cerr << "try " << mid << endl;*/ if (can_put_away(layers, A, B, mid)) hi = mid; else lo = mid + 1; } return lo; }
#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...