Submission #483539

#	Time	Username	Problem	Language	Result	Execution time	Memory
483539		MilosMilutinovic	Robots (IOI13_robots)	C++14	100 / 100	2040 ms	29008 KiB

robots

/**
 *    author: m371
 *    created: 29.10.2021 14:34:19
**/
#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

int putaway(int a, int b, int t, int* x, int* y, int* w, int* s) {
  vector<int> ord_x(a);
  iota(ord_x.begin(), ord_x.end(), 0);
  sort(ord_x.begin(), ord_x.end(), [&](int i, int j) {
    return x[i] < x[j];
  });
  vector<int> ord_y(b);
  iota(ord_y.begin(), ord_y.end(), 0);
  sort(ord_y.begin(), ord_y.end(), [&](int i, int j) {
    return y[i] < y[j];
  });
  vector<int> ord_w(t);
  iota(ord_w.begin(), ord_w.end(), 0);
  sort(ord_w.begin(), ord_w.end(), [&](int i, int j) {
    return w[i] < w[j];
  });
  vector<int> ord_s(t);
  iota(ord_s.begin(), ord_s.end(), 0);
  sort(ord_s.begin(), ord_s.end(), [&](int i, int j) {
    return s[i] < s[j];
  });
  auto Can = [&](int S) {
    int ptr = 0;
    priority_queue<pair<int, int>> st;
    vector<bool> was(t, false);
    for (int i = 0; i < a; i++) {
      while (ptr < t && w[ord_w[ptr]] < x[ord_x[i]]) {
        st.push({s[ord_w[ptr]], ord_w[ptr]});
        ptr++;
      }
      int cnt = 0;
      while (!st.empty() && cnt < S) {
        pair<int, int> it = st.top();
        was[it.second] = true;
        cnt += 1;
        st.pop();
      }
    }
    while (!st.empty()) {
      st.pop();
    }
    ptr = 0;
    for (int i = 0; i < b; i++) {
      while (ptr < t && s[ord_s[ptr]] < y[ord_y[i]]) {
        if (!was[ord_s[ptr]]) {
          st.push({w[ord_s[ptr]], ord_s[ptr]});
        }
        ptr++;
      }
      int cnt = 0;
      while (!st.empty() && cnt < S) {
        pair<int, int> it = st.top();
        was[it.second] = true;
        cnt += 1;
        st.pop();
      }
    }
    for (int i = 0; i < t; i++) {
      if (!was[i]) {
        return false;
      }
    }
    return true;
  };
  if (!Can(t)) {
    return -1;
  }
  int low = 1, high = t, ans = 0;
  while (low <= high) {
    int mid = (low + high) >> 1;
    if (Can(mid)) {
      ans = mid;
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return ans;
}

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