Submission #761484

#	Time	Username	Problem	Language	Result	Execution time	Memory
761484		nicksms	Robots (IOI13_robots)	C++17	0 / 100	1 ms	340 KiB

robots

#include "robots.h"
/**
 *      Author:  Nicholas Winschel
 *      Created: 06.19.2023 14:12:26
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
const int MAXN = 1e6 + 5;
const int MAXA = 5e4 + 5;
bool rem[MAXN];
int inds[MAXN], inds2[MAXN];
int fi[MAXA];
int cur[MAXA];
int alo[MAXA];

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
	if (A) sort(X, X+A);
	if (B) sort(Y, Y+B);
	iota(inds, inds+T, 0);
	iota(inds2, inds2+T, 0);
	sort(inds, inds+T, [&](int a, int b) {return W[a] < W[b];});
	sort(inds2, inds2+T, [&](int a, int b) {return S[a] < S[b];});
	int cp = 1;
  for (int i = 0; i < T; i++)
    while (cp <= A && X[cp-1] <= W[inds[i]]) fi[cp++]=i;
  if (W[inds[T-1]] < X[A-1]) fi[A]=T;
  for (int i = 0; i < A; i++)
    sort(inds+fi[i], inds+fi[i+1], [&](int a, int b) {
      return S[a] > S[b];
    });
  auto chk = [&](int d) -> bool {
    // cerr << "call " << d << endl;
    for (int i = 0; i < T; i++) rem[i]=true;
    for (int i = 0; i < A; i++) cur[i]=fi[i];
    for (int i = 0; i < B; i++) alo[i]=d;
    using pr = pair<int, int>;
    priority_queue<pr> h;
    int cnt = 0;
    for (int i = 0; i < A; i++) {
      if (fi[i] < fi[i+1]) h.emplace(S[inds[fi[i]]], i);
      int k = d;
      while (sz(h) && k > 0) {
        k--;
        auto [x, y] = h.top();
        h.pop();
        cnt++;
        // cerr << "mch " << inds[cur[y]] << " to rob " << i << endl;
        rem[inds[cur[y]++]]=false;
        if (cur[y] < fi[y+1]) h.emplace(S[inds[cur[y]]], y);
      }
    }
    if (cnt == T) return true;
    int p1 = 0, p2 = 0;
    while (p1 < B && p2 < T) {
      if (!rem[inds2[p2]]) {
        // cerr << "skip " << inds2[p2] << endl;
        p2++;
        continue;
      }
      if (alo[p1]==0) {
        p1++;
        continue;
      }
      if (Y[p1] <= S[inds2[p2]]) {
        p1++;
        continue;
      }
      alo[p1]--,rem[inds2[p2]]=false;
    }
    return p2 == T;
  };
  if (!chk(T)) return -1;
  int bl = -1,br=T;
  while (br - bl > 1) {
    int d = (br + bl) >> 1;
    if (chk(d)) br = d;
    else bl = d;
  }
  
	return br;
}

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