Submission #1208776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208776		pera	Robots (IOI13_robots)	C++20	76 / 100	3095 ms	10672 KiB

robots

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

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
   sort(X , X + A);
   sort(Y , Y + B);
   auto igA = [&](int x){
      int p = -1;
      for(int bit = 17;bit >= 0;bit --){
         p += 1 << bit;
         if(p >= A){
            p -= 1 << bit;
         }else if(X[p] > x){
            p -= 1 << bit;
         }
      }
      ++p;
      return A - p;
   };
   auto igB = [&](int x){
      int p = -1;
      for(int bit = 17;bit >= 0;bit --){
         p += 1 << bit;
         if(p >= B){
            p -= 1 << bit;
         }else if(Y[p] > x){
            p -= 1 << bit;
         }
      }
      ++p;
      return B - p;
   };
   vector<int> cA(T) , cB(T);
   for(int i = 0;i < T;i ++){
      cA[i] = igA(W[i]);
      cB[i] = igB(S[i]);
      if(cA[i] + cB[i] == 0){
         return -1;
      }
   }
   vector<int> oy(T);
   iota(oy.begin() , oy.end() , 0);
   sort(oy.begin() , oy.end() , [&](int i , int j){
      return pair<int , int>{cB[i] , -cA[i]} < pair<int , int>{cB[j] , -cA[j]};
   });
   reverse(oy.begin() , oy.end());
   auto solveB = [&](vector<int> v){
      vector<int> c(B + 1);
      for(int x : v){
         c[x]++;
      }
      int ans = 0;
      for(int i = 1;i <= B;i ++){
         c[i] += c[i - 1];
         ans = max(ans , (c[i] + i - 1) / i);
      }
      return ans;
   };
   auto pos = [&](int v){
      int _A = min(A , (T + v - 1) / v);
      vector<int> pref(_A + 1) , left;
      for(int i = 1;i <= _A;i ++){
         pref[i] = i * v;
      }
      auto can_insert = [&](int x){
         int mn = 1E9;
         for(int i = _A;i >= x;i --){
            mn = min(mn , pref[i]);
         }
         return mn > 0;
         //return (query(1 , 1 , A , x , A) > 0);
      };
      auto insert = [&](int x){
         for(int i = _A;i >= x;i --){
            --pref[i];
         }
        // update(1 , 1 , A , x , A , -1);
      };
      for(int i = 0;i < T;i ++){
         if(!cA[i]){
            left.emplace_back(cB[i]);
         }else if(!cB[i]){
            if(!can_insert(cA[i])){
               return false;
            }
            insert(cA[i]);
         }
      }
      for(int i = T - 1;i >= 0;i --){
         int j = oy[i];
         if(!cA[j] || !cB[j]){
            continue;
         }
         if(can_insert(cA[j])){
            insert(cA[j]);
         }else{
            left.emplace_back(cB[j]);
         }
      }
      return solveB(left) <= v;
   };
   int ans = 0;
   for(int bit = 20;bit >= 0;bit --){
      ans += 1 << bit;
      if(pos(ans) == true){
         ans -= 1 << bit;
      }
   }
   ++ans;
   return ans;
}

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