Submission #514862

#	Time	Username	Problem	Language	Result	Execution time	Memory
514862		600Mihnea	Robots (IOI13_robots)	C++17	14 / 100	130 ms	8776 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 1e6 + 7;
const int L = 1000 + 7;
int cover1[N], cover2[N];
int cnt[L][L];
bool is[L][L];

int putaway(int sz1, int sz2, int n, int val1[], int val2[], int x[], int y[]) {
  assert(sz1 < L);
  assert(sz2 < L);
  vector<pair<int, int>> xx, yy;
  for (int i = 0; i < n; i++) {
    xx.push_back({x[i], i});
    yy.push_back({y[i], i});
    cover1[i] = -1;
    cover2[i] = -1;
  }
  sort(xx.rbegin(), xx.rend());
  sort(yy.rbegin(), yy.rend());

  for (int i = 0; i < sz1; i++) {
    val1[i]--;
  }
  for (int i = 0; i < sz2; i++) {
    val2[i]--;
  }
  sort(val1, val1 + sz1); reverse(val1, val1 + sz1);
  sort(val2, val2 + sz2); reverse(val2, val2 + sz2);
  {
    int p1 = 0;
    for (auto &it : xx) {
      while (p1 < sz1 && it.first <= val1[p1]) p1++;
      cover1[it.second] = p1;
    }
  }
  {
    int p2 = 0;
    for (auto &it : yy) {
      while (p2 < sz2 && it.first <= val2[p2]) p2++;
      cover2[it.second] = p2;
    }
  }
  for (int i = 0; i < n; i++) {
    assert(0 <= cover1[i] && cover1[i] <= sz1);
    assert(0 <= cover2[i] && cover2[i] <= sz2);
    is[cover1[i]][cover2[i]] = 1;
    cnt[cover1[i]][cover2[i]]++;
  }
  for (int i = 0; i <= sz1; i++) {
    for (int j = 1; j <= sz2; j++) {
      cnt[i][j] += cnt[i][j - 1];
    }
  }
  for (int i = 1; i <= sz1; i++) {
    for (int j = 0; j <= sz2; j++) {
      cnt[i][j] += cnt[i - 1][j];
    }
  }
  if (cnt[0][0]) {
    return -1;
  }
  int mx = 0;
  for (int i = 0; i <= sz1; i++) {
    for (int j = 0; j <= sz2; j++) {
      if (!is[i][j]) {
        continue;
      }
      assert(i + j > 0);
      int up = cnt[i][j];
      int down = i + j;
      int smth = (up + down - 1) / down;
      mx = max(mx, smth);
    }
  }

  return mx;
}

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