Submission #982892

#	Time	Username	Problem	Language	Result	Execution time	Memory
982892		hyakup	Robots (IOI13_robots)	C++17	100 / 100	2971 ms	26448 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int inf = 2e9 + 10;
const int maxn = 5e4 + 10;
const int maxt = 1e6 + 10;

int wbots[maxn], sbots[maxn];
struct Toy{
  int w, s; Toy( int w = 0, int s = 0 ): w(w), s(s) {}
  bool operator < ( Toy t ){ return (( s == t.s ) ? w > t.w : s > t.s ); }
} toys[maxt];

bool check( int A, int B, int T, int k ){
  multiset<pair<int, int>> s;
  for( int i = 0; i < A; i++ ) s.insert({ wbots[i] - 1, k });
  ll cont = 0, i = 0; 
  for( int t = 0; t < T; t++ ){
    Toy cur = toys[t];
    for( i; i < B && sbots[i] > cur.s; i++ ) cont += k;
    auto it = s.lower_bound({ cur.w, 0 });
    if( it == s.end() ){
      if( cont ){ cont--; continue; }
      return false;
    }
    auto [val, qtd] = *it;
    s.erase(it);
    if( qtd > 1 ) s.insert({ val, qtd - 1 });
  }
  return true;
}

int bs( int A, int B, int T ){
  int l = (T + A + B - 1)/( A + B ), r = T + 1;
  while( l < r ){
    int mid = ( l + r )/2;
    if( check( A, B, T, mid ) ) r = mid;
    else l = mid + 1;
  }
  return ( r == T + 1 ) ? -1 : r;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
  for( int i = 0; i < A; i++ ) wbots[i] = X[i];
  for( int i = 0; i < B; i++ ) sbots[i] = Y[i];
  for( int i = 0; i < T; i++ ) toys[i] = Toy( W[i], S[i] );
  sort( wbots, wbots + A );
  sort( sbots, sbots + B, greater<int>() );
  sort( toys, toys + T );
  return bs( A, B, T );
}

Compilation message (stderr)

robots.cpp: In function 'bool check(int, int, int, int)':
robots.cpp:22:10: warning: statement has no effect [-Wunused-value]
   22 |     for( i; i < B && sbots[i] > cur.s; i++ ) cont += k;
      |          ^

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