Submission #1136914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136914		mychecksedad	Robots (IOI13_robots)	C++20	76 / 100	3096 ms	67076 KiB

robots

/* Author : Mychecksdead  */
#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
  int ans = -1;
  int l = 1, r = T;
  if(A>0)
    sort(X, X+A);  
  if(B>0)
    sort(Y, Y+B);  

  while(l <= r){
    int m = l+r>>1;
    set<array<int, 3>> x, y;
    for(int i = 0; i < T; ++i){
      x.insert({W[i], S[i], i});
      y.insert({S[i], W[i], i});
    }
    set<array<int, 3>> x2, y2;

    for(int i = 0; i < A; ++i){
      while(!x.empty() && (*x.begin())[0] < X[i]){
        x2.insert(array<int, 3>{-(*x.begin())[1], (*x.begin())[0], (*x.begin())[2]});
        x.erase(x.begin());
      }
      for(int j = 0; j < m; ++j){
        if(x2.empty()) break;
        auto it = x2.begin();
        // cout << (*it)[0] << ' ' << (*it)[1] << ' ' << (*it)[2] << '\n';
        auto ff = y.lower_bound(array<int,3>{-(*it)[0], (*it)[1], (*it)[2]});
        if(ff == y.end() || (*ff) != array<int,3>{-(*it)[0], (*it)[1], (*it)[2]}){
          cout << "wtf";
          return -1;
        }
        // assert(ff != y.end() && (*ff) == array<int,3>{-(*it)[0], (*it)[1], (*it)[2]});
        y.erase(array<int,3>{-(*it)[0], (*it)[1], (*it)[2]});
        x2.erase(it);
      }
    }
    // cout << y.size() << "afuq\n";
    for(int i = 0; i < B; ++i){
      while(!y.empty() && (*y.begin())[0] < Y[i]){
        y2.insert(array<int, 3>{-(*y.begin())[1], (*y.begin())[0], (*y.begin())[2]});
        y.erase(y.begin());
      }
      for(int j = 0; j < m; ++j){
        if(y2.empty()) break;
        auto it = y2.begin();
        y2.erase(it);
      }
    }
    if(y.empty() && y2.empty()){
      ans = m;
      r = m - 1;
    }else l = m + 1;
    // cout << m  << '\n';
  }


  return ans;
}

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