제출 #1208714

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208714		pera	Robots (IOI13_robots)	C++20	39 / 100	150 ms	12544 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> ox(T) , oy(T);
   iota(ox.begin() , ox.end() , 0);
   iota(oy.begin() , oy.end() , 0);
   sort(ox.begin() , ox.end() , [&](int i , int j){
      return pair<int , int>{cA[i] , -cB[i]} < pair<int , int>{cA[j] , -cB[j]};
   });
   sort(oy.begin() , oy.end() , [&](int i , int j){
      return pair<int , int>{cB[i] , -cA[i]} < pair<int , int>{cB[j] , -cA[j]};
   });
   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){
      vector<int> pref(A + 1) , left;
      auto can_insert = [&](int x){
         for(int i = 1;i <= A;i ++){
            if((pref[i] + (i >= x)) > i * v){
               return false;
            }
         }
         return true;
      };
      auto insert = [&](int x){
         for(int i = x;i <= A;i ++){
            ++pref[i];
         }
      };
      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: 0 / 37
• Subtask 5: 0 / 10