| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 257844 | ChrisT | Robots (IOI13_robots) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.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;
}