Submission #592766

#	Time	Username	Problem	Language	Result	Execution time	Memory
592766		Mamedov	Robots (IOI13_robots)	C++17	100 / 100	1490 ms	24356 KiB

robots

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include "robots.h"
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

bool check(int A, int B, int T, int H, int X[], int Y[], int W[], int S[]) {
  int k = 0;
  priority_queue<int>Ss;
  for (int i = 0; i < A; ++i) {
    while (k < T && W[k] < X[i]) {
      Ss.push(S[k]);
      ++k;
    }
    for (int j = 0; j < H && !Ss.empty(); ++j) {
      Ss.pop();
    }
  }
  while(k < T) {
    Ss.push(S[k]);
    ++k;
  }
  for (int i = 0; i < B && !Ss.empty() && Ss.top() < Y[i]; ++i) {
    for (int j = 0; j < H && !Ss.empty(); ++j) {
      Ss.pop();
    }
  }
  return Ss.empty();
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
  sort(X, X + A);
  sort(Y, Y + B);
  reverse(Y, Y + B);
  vector<pii>toys(T);
  for (int i = 0; i < T; ++i) {
    toys[i] = mpr(W[i], -S[i]);
  }
  sort(all(toys));
  for (int i = 0; i < T; ++i) {
    W[i] = toys[i].f;
    S[i] = -toys[i].s;
  }

  int l = 1, r = T + 1;
  int mid;
  while (l < r) {
    mid = (l + r) >> 1;
    if (check(A, B, T, mid, X, Y, W, S)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  if (r == T + 1) r = -1;
  return r;
}

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