Submission #257845

#	Time	Username	Problem	Language	Result	Execution time	Memory
257845		ChrisT	Robots (IOI13_robots)	C++17	76 / 100	821 ms	65540 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std; //testing if this greedy works
using ll = long long;
using pii = pair<int,int>;
const int MN = 5e4 + 5, LOG = 18, MOD = 1e9 + 7;
struct Point {
  int x,y;
  bool operator< (const Point &o) const {
    return make_pair(x,y) < make_pair(o.x,o.y);
  }
};
struct cmp {
  bool operator() (const Point &a, const Point &b) const {
    return make_pair(a.y,a.x) < make_pair(b.y,b.x);
  }
};
int putaway (int a, int b, int t, int *x, int *y, int *w, int *s) {
  sort(x,x+a); sort(y,y+b);
  map<Point,int> taken; vector<Point> xSrt(t), ySrt(t);
  for (int i = 0; i < t; i++) xSrt[i] = ySrt[i] = {w[i],s[i]};
  sort(xSrt.begin(),xSrt.end()); sort(ySrt.begin(),ySrt.end(),[](const Point &aa, const Point &bb){return aa.y < bb.y;});
  int ret = 0, done = 0;
  while (done < t) {
    ++ret; multiset<Point,cmp> high; bool took = 0; map<Point,int> seen;
    int id = 0;
    for (int i = 0; i < a; i++) {
      while (id < t && xSrt[id].x < x[i]) {
        if (++seen[xSrt[id]] > taken[xSrt[id]]) 
          high.insert(xSrt[id]);
        ++id;
      }
      if (!high.empty()) taken[*high.rbegin()]++, high.erase(prev(high.end())), took = 1, ++done;
    }
    multiset<Point> r; id = 0; seen.clear();
    for (int i = 0; i < b; i++) {
      while (id < t && ySrt[id].y < y[i]) {
        if (++seen[ySrt[id]] > taken[ySrt[id]])
          r.insert(ySrt[id]);
        ++id;
      }
      if (!r.empty()) taken[*r.rbegin()]++, r.erase(prev(r.end())), took = 1, ++done;
    }
    if (!took) return -1;
  }
  return ret;
}

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