Submission #1014526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014526		huutuan	Robots (IOI13_robots)	C++14	76 / 100	108 ms	9660 KiB

robots

#include "robots.h"

#include <bits/stdc++.h>

using namespace std;

int pf[1010][1010], X[50010], Y[50010];

int sum(int x, int y, int z, int t){
   if (x>z || y>t) return 0;
   return pf[z][t]-pf[x-1][t]-pf[z][y-1]+pf[x-1][y-1];
}

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]-1;
   for (int i=0; i<B; ++i) Y[i+1]=_Y[i]-1;
   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) ++pf[W[i]][S[i]];
   for (int i=1; i<=1000; ++i) for (int j=1; j<=1000; ++j){
      pf[i][j]+=pf[i-1][j]+pf[i][j-1]-pf[i-1][j-1];
   }
   int l=1, r=T;
   while (l<=r){
      int mid=(l+r)>>1;
      bool check=1;
      for (int i=0; i<=A; ++i){
         check&=sum(X[i]+1, Y[0]+1, 1000, 1000)<=(A-i+B-0)*mid;
         check&=sum(X[i]+1, Y[B]+1, 1000, 1000)<=(A-i+B-B)*mid;
      }
      for (int i=0; i<=B; ++i){
         check&=sum(X[0]+1, Y[i]+1, 1000, 1000)<=(A-0+B-i)*mid;
         check&=sum(X[A]+1, Y[i]+1, 1000, 1000)<=(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: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10