Submission #1136920

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136920		mychecksedad	Robots (IOI13_robots)	C++20	100 / 100	1268 ms	24608 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);  

  vector<array<int, 3>> x, y;
  for(int i = 1; i <= T; ++i){
    x.pb({W[i-1], S[i-1], i-1});
    y.pb({S[i-1], W[i-1], i-1});
  }
  sort(all(x));
  sort(all(y));

  while(l <= r){
    int m = l+r>>1;
    priority_queue<pair<int, int>> x2;
    int px = 0, py = 0;
    bitset<1000007> vis = 0;    
    for(int i = 0; i < A; ++i){
      while(px < T && x[px][0] < X[i]){
        x2.push(pii{x[px][1], x[px][2]});
        ++px;
      }
      for(int j = 0; j < m; ++j){
        if(x2.empty()) break;
        auto it = x2.top();
        vis[it.ss] = 1;
        x2.pop();
      }
    }
    int cc = 0;
    for(int i = 0; i < B; ++i){
      while(py < T && (vis[y[py][2]] || y[py][0] < Y[i])){
        if(vis[y[py][2]]){
          ++py;
          continue;
        }
        cc++;
        ++py;
      }
      for(int j = 0; j < m; ++j){
        if(cc == 0) break;
        --cc;
      }
    }
    while(py < T && vis[y[py][2]]) ++py;
    if(py == T && cc == 0){
      ans = m;
      r = m - 1;
    }else l = m + 1;
    // cout << m  << '\n';
  }


  return ans;
}

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