Submission #38667

#	Time	Username	Problem	Language	Result	Execution time	Memory
38667		funcsr	Robots (IOI13_robots)	C++14	100 / 100	2336 ms	13208 KiB

robots

#include "robots.h"
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define pb push_back
#define _1 first
#define _2 second
#define INF 2001000000
#define MOD 1000000007

struct BIT {
  int xs[50002];
  int c = 0;
  const int n = 50001;
  void init() {
    c = 0;
    rep(i, n+1) xs[i] = 0;
  }
  void add(int i, int v) {
    for (int x=i+1; x<=n; x+=x&-x) xs[x] += v;
    c += v;
  }
  int sum(int i) {
    int s = 0;
    for (int x=i+1; x>0; x-=x&-x) s += xs[x];
    return s;
  }
  int largest() {
    int x = 0, v = c;
    for (int k=1<<15; k>0; k>>=1) {
      if (x+k <= n && xs[x+k] < v) v -= xs[x+k], x += k;
    }
    return x;
  }
};

int N, A, B;
int F[50000];
int C[50001];
vector<int> G[50001];
vector<int> xs, ys;
BIT bit;

bool f(int X) {
  bit.init();
  rep(x, xs.size()) {
    for (int y : G[x]) bit.add(y, 1);
    int times = min(1LL*X*C[x], (long long)N);
    while (bit.c > 0 && times > 0) {
      bit.add(bit.largest(), -1);
      times--;
    }
  }
  for (int i=B-1; i>=0; i--) {
    rep(_, X) {
      if (bit.c == 0) return true;
      int x = bit.largest();
      if (x > F[i]) return false;
      bit.add(x, -1);
    }
  }
  return bit.c == 0;
}

int putaway(int AA, int BB, int T, int X[], int Y[], int W[], int S[]) {
  N = T, A = AA, B = BB;
  rep(i, A) X[i]--;
  rep(i, B) Y[i]--;
  sort(X, X+A);
  sort(Y, Y+B);
  int max_x = -1, max_y = -1;
  rep(i, A) max_x = max(max_x, X[i]);
  rep(i, B) max_y = max(max_y, Y[i]);
  rep(i, T) if (W[i] > max_x && S[i] > max_y) return -1;
  rep(i, A) xs.pb(X[i]);
  rep(i, B) ys.pb(Y[i]);
  xs.pb(INF);
  ys.pb(INF);
  sort(all(xs)); uniq(xs);
  sort(all(ys)); uniq(ys);
  rep(i, A) X[i] = index(xs, X[i]);
  rep(i, B) Y[i] = index(ys, Y[i]);
  rep(i, A) C[X[i]]++;
  rep(i, B) F[i] = Y[i];
  rep(i, N) {
    W[i] = index(xs, W[i]);
    S[i] = index(ys, S[i]);
    G[W[i]].pb(S[i]);
  }

  int lo = 0, hi = N;
  while (hi-lo > 1) {
    int mid = (lo+hi)/2;
    if (f(mid)) hi = mid;
    else lo = mid;
  }
  return hi;
}

Compilation message (stderr)

robots.cpp: In function 'bool f(int)':
robots.cpp:12:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, n) for (int i=0; i<(n); i++)
                                  ^
robots.cpp:57:3: note: in expansion of macro 'rep'
   rep(x, xs.size()) {
   ^

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