Submission #1259695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259695		comgaTramAnh	Robots (IOI13_robots)	C++20	90 / 100	3093 ms	15188 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());
  sort(X, X + A);  
  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 {
        notChoose.push_back(i); 
      } 
    }
    reverse(notChoose.begin(), notChoose.end());
    bool ok = true; 
    int p = A - 1; 
    for (int i = (int) notChoose.size() - 1; i >= 0; i--) {
      while (p >= 0 && save[notChoose[i]].first >= X[p]) {
        p--; 
      }
      if (p < 0) {
        ok = false;
        break; 
      }
      if (save[notChoose[i]].first < X[p]) {
        numbWeak[p]++; 
        if (numbWeak[p] == mid) {
          p--; 
        }
      }
      else {
        ok = false; 
        break; 
      }      
    }
    if (ok == 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