Submission #377035

#	Time	Username	Problem	Language	Result	Execution time	Memory
377035		WLZ	Robots (IOI13_robots)	C++14	100 / 100	1861 ms	24824 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> x, y;
vector< pair<int, int> > toys;

bool check(int k) {
  priority_queue<int> pq;
  int cnt = 0, ptr = 0;
  for (int i = 0; i < (int) x.size(); i++) {
    while (ptr < n && toys[ptr].first < x[i]) {
      pq.push(toys[ptr].second);
      ptr++;
    }
    for (int j = 0; j < k && !pq.empty(); j++) {
      pq.pop();
    }
  }
  while (ptr < n) pq.push(toys[ptr++].second);
  for (int i = 0; i < (int) y.size(); i++) {
    for (int j = 0; j < k && !pq.empty(); j++) {
      if (pq.top() >= y[i]) return false;
      pq.pop();
    }
  }
  return pq.empty();
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
  n = T;
  x.assign(X, X + A); y.assign(Y, Y + B);
  sort(x.begin(), x.end());
  sort(y.rbegin(), y.rend());
  for (int i = 0; i < n; i++) toys.push_back({W[i], S[i]});
  sort(toys.begin(), toys.end());
  if (!check(T)) return -1;
  int lo = 1, hi = T;
  while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (check(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Compilation message (stderr)

robots.cpp: In function 'bool check(int)':
robots.cpp:11:7: warning: unused variable 'cnt' [-Wunused-variable]
   11 |   int cnt = 0, ptr = 0;
      |       ^~~

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