Submission #990622

#	Time	Username	Problem	Language	Result	Execution time	Memory
990622		AdamGS	Robots (IOI13_robots)	C++17	100 / 100	236 ms	28244 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e6+7, INF=1e9+7;
int A, B, n, X[LIM], Y[LIM], odw[LIM], F[LIM], ile[LIM], sum[LIM];
pair<int,int>T[LIM];
int fnd(int x) {
  if(F[x]==x) return x;
  return F[x]=fnd(F[x]);
}
void uni(int a, int b) {
  ile[fnd(b)]+=ile[fnd(a)];
  F[fnd(a)]=fnd(b);
}
bool check(int x) {
  rep(i, B+1) {
    F[i]=i;
    ile[i]=x;
  }
  ile[B]=0;
  rep(i, A+1) sum[i]=0;
  rep(i, n) {
    while(ile[fnd(T[i].nd)]==0) {
      if(fnd(T[i].nd)==B) break;
      uni(T[i].nd, fnd(T[i].nd)+1);
    }
    if(ile[fnd(T[i].nd)]) {
      --ile[fnd(T[i].nd)];
      continue;
    }
    ++sum[T[i].st];
  }
  ll akt=-x;
  for(int i=A; i>=0; --i) {
    akt+=x;
    akt-=sum[i];
    if(akt<0) return false;
  }
  return true;
}
int putaway(int Ai, int Bi, int Ti, int Xi[], int Yi[], int Wi[], int Si[]) {
  A=Ai; B=Bi; n=Ti;
  rep(i, A) X[i]=Xi[i];
  rep(i, B) Y[i]=Yi[i];
  rep(i, n) T[i]={Wi[i], Si[i]};
  sort(T, T+n);
  sort(X, X+A);
  sort(Y, Y+B);
  if(A==0) X[A++]=0;
  if(B==0) Y[B++]=0;
  rep(i, n) if(T[i].st>=X[A-1] && T[i].nd>=Y[B-1]) return -1;
  X[A]=Y[B]=INF;
  rep(i, n) {
    int po=0, ko=A;
    while(po<ko) {
      int sr=(po+ko)/2;
      if(T[i].st>=X[sr]) po=sr+1; else ko=sr;
    }
    T[i].st=po;
    po=0; ko=B;
    while(po<ko) {
      int sr=(po+ko)/2;
      if(T[i].nd>=Y[sr]) po=sr+1; else ko=sr;
    }
    T[i].nd=po;
  }
  sort(T, T+n);
  reverse(T, T+n);
  int po=1, ko=n;
  while(po<ko) {
    int sr=(po+ko)/2;
    if(check(sr)) ko=sr; else po=sr+1;
  }
  return po;
}

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