Submission #1263825

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263825		repmann	Robots (IOI13_robots)	C++20	100 / 100	1208 ms	12648 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
int A, B, T;
int putaway(int a, int b, int t, int *X, int *Y, int *W, int *S)
{
  A = a;
  B = b;
  T = t;
  sort(X, X + A);
  sort(Y, Y + B);
  for(int i = 0; i < T; i++) if((!A || (W[i] >= X[A - 1])) && (!B || (S[i] >= Y[B - 1]))) return -1;
  vector <pair <int, int>> V;
  for(int i = 0; i < T; i++) V.push_back({W[i], S[i]});
  sort(V.begin(), V.end());
  int ret = -1, l = 1, r = T, s;
  auto OK = [&]()
  {
    priority_queue <int> H;
    int j = 0;
    for(int i = 0; i < A; i++)
    {
      while((j < T) && (V[j].first < X[i])) {H.push(V[j].second); j++;}
      for(int k = 0; (k < s) && H.size(); k++) H.pop();
    }
    for(j; j < T; j++) H.push(V[j].second);
    for(int i = B - 1; i >= 0; i--)
    {
      for(int k = 0; (k < s) && H.size(); k++)
      {
        if(H.top() >= Y[i]) return false;
        H.pop();
      }
    }
    return !H.size();
  };
  while(l <= r)
  {
    s = (l + r) >> 1;
    if(!OK()) l = s + 1;
    else {r = s - 1; ret = s;}
  }
  return ret;
}
//int main()
//{
//  int 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];
//  for(int i = 0; i < t; i++) cin >> s[i];
//  cout << putaway(a, b, t, x, y, w, s) << '\n';
//  return 0;
//}

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