Submission #990617

#	Time	Username	Problem	Language	Result	Execution time	Memory
990617		AdamGS	Robots (IOI13_robots)	C++17	0 / 100	2 ms	16828 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;
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);
    rep(i, n) if(T[i].st>=X[A-1] && T[i].nd>=Y[B-1]) return -1;
    rep(i, n) {
      int po=0, ko=A;
      while(po<ko) {
        int sr=(po+ko+1)/2;
        if(T[i].st>=X[sr]) ko=sr-1; else po=sr;
      }
      T[i].st=po;
      po=0; ko=B;
      while(po<ko) {
        int sr=(po+ko+1)/2;
        if(T[i].nd>=Y[sr]) ko=sr-1; else po=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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10