Submission #102949

#	Time	Username	Problem	Language	Result	Execution time	Memory
102949		wxh010910	Robots (IOI13_robots)	C++17	0 / 100	3 ms	384 KiB

robots

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

using namespace std;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
  sort(X, X + A);
  sort(Y, Y + B);
  vector<pair<int, int>> p(T);
  for (int i = 0; i < T; ++i) {
    p[i] = make_pair(W[i], S[i]);
    if ((!A || W[i] >= X[A - 1]) && (!B || S[i] >= Y[B - 1])) {
      return -1;
    }
  }
  sort(p.begin(), p.end());
  auto check = [&](int t) {
    priority_queue<int> q;
    int ptr = 0;
    for (int i = 0; i < A; ++i) {
      while (ptr < T && p[ptr].first < X[i]) {
        q.push(p[ptr++].second);
      }
      for (int j = 0; j < t && !q.empty(); ++j) {
        q.pop();
      }
    }
    while (ptr < T) {
      q.push(p[ptr++].second);
    }
    for (int i = B - 1; ~i; --i) {
      for (int j = 0; j < t && !q.empty(); ++j) {
        if (q.top() >= Y[i]) {
          return false;
        }
        q.pop();
      }
    }
    return true;
  };
  int l = 1, r = T;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (check(mid)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return r;
}

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