이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |