제출 #1231501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231501		kunzaZa183	Robots (IOI13_robots)	C++20	100 / 100	2094 ms	10688 KiB

robots

#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[]) {
  sort(X, X + A);
  sort(Y, Y + B, greater<int>());

  for (int i = 0; i < T; i++)
    if (X[A - 1] <= W[i] && Y[0] <= S[i])
      return -1;

  int l = 1, r = T;

  while (l < r) {

    int mid = (l + r) / 2;

    vector<int> vi(T);
    iota(vi.begin(), vi.end(), 0);
    sort(vi.begin(), vi.end(), [&](int a, int b) { return W[a] < W[b]; });

    priority_queue<int> pqi;
    int in = 0;
    for (int i = 0; i < A; i++) {
      while (in < vi.size()) {
        if (W[vi[in]] < X[i]) {
          // cout << "IN " << mid << " " << S[vi[in]] << "\n";
          pqi.push(S[vi[in]]);
          in++;
        } else
          break;
      }

      for (int j = 0; j < mid && !pqi.empty(); j++) {
        // cout << "OUT " << mid << " " << pqi.top() << "\n";
        pqi.pop();
      }
    }

    // cout << "X\n";

    while (in < vi.size()) {
      // cout << "IN " << mid << " " << S[vi[in]] << "\n";
      pqi.push(S[vi[in]]);
      in++;
    }

    for (int i = 0; i < B; i++) {
      for (int j = 0; j < mid && !pqi.empty() && Y[i] > pqi.top(); j++) {
        // cout << "OUT " << mid << " " << pqi.top() << "\n";
        pqi.pop();
      }
    }

    if (pqi.empty()) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }

  return l;
}

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