Submission #1014532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014532		huutuan	Robots (IOI13_robots)	C++14	100 / 100	196 ms	18120 KiB

robots

#include "robots.h"

#include <bits/stdc++.h>

using namespace std;

const int N=5e4+10, inf=1e9;

#define y1 amongus

int X[N], Y[N];
int x1[N], x2[N], y1[N], y2[N];

int putaway(int A, int B, int T, int _X[], int _Y[], int W[], int S[]) {
   for (int i=0; i<A; ++i) X[i+1]=_X[i];
   for (int i=0; i<B; ++i) Y[i+1]=_Y[i];
   for (int i=0; i<T; ++i) ++W[i], ++S[i];
   sort(X+1, X+A+1);
   sort(Y+1, Y+B+1);
   vector<int> vx(X+1, X+A+1), vy(Y+1, Y+B+1); vx.push_back(-1); vy.push_back(-1);
   sort(vx.begin(), vx.end()); sort(vy.begin(), vy.end());
   vx.resize(unique(vx.begin(), vx.end())-vx.begin());
   vy.resize(unique(vy.begin(), vy.end())-vy.begin());
   for (int i=1; i<=A; ++i) X[i]=lower_bound(vx.begin(), vx.end(), X[i])-vx.begin();
   for (int i=1; i<=B; ++i) Y[i]=lower_bound(vy.begin(), vy.end(), Y[i])-vy.begin();
   for (int i=0; i<T; ++i){
      W[i]=lower_bound(vx.begin(), vx.end(), W[i])-vx.begin();
      S[i]=lower_bound(vy.begin(), vy.end(), S[i])-vy.begin();
   }
   for (int i=0; i<T; ++i){
      ++x1[W[i]];
      if (S[i]>Y[B]) ++x2[W[i]];
      ++y1[S[i]];
      if (W[i]>X[A]) ++y2[S[i]];
   }
   partial_sum(x1, x1+N, x1);
   partial_sum(x2, x2+N, x2);
   partial_sum(y1, y1+N, y1);
   partial_sum(y2, y2+N, y2);
   int l=1, r=T;
   while (l<=r){
      int mid=(l+r)>>1;
      bool check=1;
      for (int i=0; i<=A; ++i){
         check&=x1[(int)vx.size()]-x1[X[i]]<=1ll*(A-i+B-0)*mid;
         check&=x2[(int)vx.size()]-x2[X[i]]<=1ll*(A-i+B-B)*mid;
      }
      for (int i=0; i<=B; ++i){
         check&=y1[(int)vy.size()]-y1[Y[i]]<=1ll*(A-0+B-i)*mid;
         check&=y2[(int)vy.size()]-y2[Y[i]]<=1ll*(A-A+B-i)*mid;
      }
      if (check) r=mid-1;
      else l=mid+1;
   }
   return l==T+1?-1:l;
}

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