Submission #1259637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259637		comgaTramAnh	Robots (IOI13_robots)	C++20	90 / 100	3038 ms	15184 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std; 
long long inf = 2000000000000007LL; 

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
//int putaway(int A, int B, int T, vector <int> X, vector <int> Y, vector <int> W, vector <int> S) {
  vector <pair <int, int>> save; 
  for (int i = 0; i < T; i++) {
    save.push_back(make_pair(W[i], S[i])); 
  }
  sort(save.begin(), save.end()); 
  long long ans = -1;
  long long lo = 1, hi = inf;  
  while (lo <= hi) {
    long long mid = (lo + hi) / 2; 
    set <pair <int, int>> myset; 
    for (int i = 0; i < B; i++) {
      myset.insert(make_pair(Y[i], i)); 
    }
    vector <long long> numbWeak(A, 0), numbSmall(B, 0); 
    vector <int> notChoose;
    for (int i = T - 1; i >= 0; i--) {
      set <pair <int, int>>::iterator it = myset.lower_bound(make_pair(save[i].second, B + 10));
      if (it != myset.end()) {
        numbSmall[(*it).second]++; 
        if (numbSmall[(*it).second] == mid) {
          myset.erase(it); 
        }
      }
      else {
        //cout << i << endl;
        notChoose.push_back(i); 
      } 
    }
   // cout << "-------" << endl;
    myset.clear();
    for (int i = 0; i < A; i++) {
      myset.insert(make_pair(X[i], i)); 
    }
    reverse(notChoose.begin(), notChoose.end());
    vector <int> notChoose2;
    for (int i = (int) notChoose.size() - 1; i >= 0; i--) {
      set <pair <int, int>>::iterator it = myset.lower_bound(make_pair(save[notChoose[i]].first, A + 10));
      if (it != myset.end()) {
        //cout << (*it).second << "     " << mid << endl;
        numbWeak[(*it).second]++; 
        if (numbWeak[(*it).second] == mid) {
          myset.erase(it); 
        }
      }
      else {
        notChoose2.push_back(i); 
      }  
    }
    if (notChoose2.empty() == false) {
      lo = mid + 1; 
    } 
    else {
      ans = mid; 
      hi = mid - 1; 
    }
  }
  return ans;   
}

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