Submission #1189550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189550		spacewalker	Robots (IOI13_robots)	C++20	14 / 100	118 ms	16452 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;
namespace r = ranges;
namespace v = ranges::views;

// has to return toys sorted in decreasing y
vector<pair<int, int>> remove_one_dim(const vector<pair<int, int>> &toys,
                                      const vector<int> &limits,
                                      int toys_per_bot) {
  int ctoy = 0;
  // toys are sorted by increasing weight

  priority_queue<pair<int, int>>
      remaining_toys; // toys here are stored in (y, x) order
  for (int weight_limit : limits) {
    while (ctoy < toys.size() && toys[ctoy].first < weight_limit) {
      auto toy = toys[ctoy++];
      remaining_toys.emplace(toy.second, toy.first);
    }
    for (int i = 0; i < toys_per_bot && !remaining_toys.empty(); ++i) {
      /*auto [y, x] = remaining_toys.top();*/
      /*cerr << "weight limit " << weight_limit << " to toy " << x << " " << y
       * << endl;*/
      remaining_toys.pop();
    }
  }

  while (ctoy < toys.size()) {
    auto toy = toys[ctoy++];
    remaining_toys.emplace(toy.second, toy.first);
  }

  vector<pair<int, int>> ans;

  while (!remaining_toys.empty()) {
    auto [y, x] = remaining_toys.top();
    remaining_toys.pop();
    ans.emplace_back(x, y);
  }
  return ans;
}

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<pair<int, int>> &compressed_toys, int A, int B, int toys_per_bot) {
  cerr << "CPA == " << endl;
  vector<int> layers =
      vec_of(compressed_toys | v::transform([&](pair<int, int> p) {
               return max(A - p.first, B - p.second);
             }));

  r::sort(layers);
  int 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);

    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))};
      }));

  if (!can_put_away(compressed_toys, 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(compressed_toys, A, B, mid))
      hi = mid;
    else
      lo = mid + 1;
  }
  return lo;
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10