Submission #1264224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264224		DeltaStruct	Robots (IOI13_robots)	C++20	76 / 100	3093 ms	31776 KiB

robots

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

int putaway(int x,int y,int n,int A[],int B[],int c[],int d[]){
  vector<pair<int,int>> C; for (int i(0);i < n;++i) C.emplace_back(c[i],d[i]);
  sort(A,A+x),sort(B,B+y),sort(C.begin(),C.end());
  int l = n+1,r = 0,mid;
  while(l-r>1){
    mid = (l+r)/2;
    multiset<int> M;
    for (int i(0),k(0);i < x;++i){
      for (;k < n&&C[k].first<A[i];++k) M.emplace(C[k].second);
      for (int j(0);j < mid&&!M.empty();++j) M.erase(prev(M.end()));
    }
    for (int i(0);i < n;++i) if (A[x-1]<=C[i].first) M.emplace(C[i].second);
    for (int i(0);i < y;++i) for (int k(0);k < mid&&!M.empty()&&*M.begin()<B[i];++k) M.erase(M.begin());
    if (M.empty()) l = mid;
    else r = mid;
  }
  return (l==n+1?-1:l);
}

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