제출 #377033

#제출 시각아이디문제언어결과실행 시간메모리
377033WLZ로봇 (IOI13_robots)C++14
76 / 100
3082 ms28584 KiB
#include "robots.h" #include <bits/stdc++.h> using namespace std; struct toy { int w, s, idx; }; int n; vector<int> x, y; vector<toy> toys; bool check(int k) { vector<bool> used(n, false); sort(toys.begin(), toys.end(), [](const toy &a, const toy &b) { return a.w < b.w; }); priority_queue< pair<int, int> > pq; int cnt = 0; for (int i = 0, ptr = 0; i < (int) x.size(); i++) { while (ptr < n && toys[ptr].w < x[i]) { pq.push({toys[ptr].s, toys[ptr].idx}); ptr++; } for (int j = 0; j < k && !pq.empty(); j++) { cnt++; used[pq.top().second] = true; pq.pop(); } } sort(toys.begin(), toys.end(), [](const toy &a, const toy &b) { return a.s < b.s; }); int cur = 0; for (int i = 0, ptr = 0; i < (int) y.size(); i++) { while (ptr < n && toys[ptr].s < y[i]) { if (!used[toys[ptr].idx]) cur++; ptr++; } cnt += min(cur, k); cur -= min(cur, k); } return cnt == n; } int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { n = T; x.assign(X, X + A); y.assign(Y, Y + B); sort(x.begin(), x.end()); sort(y.begin(), y.end()); for (int i = 0; i < n; i++) toys.push_back({W[i], S[i], i}); if (!check(T)) return -1; int lo = 1, hi = T; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (check(mid)) hi = mid; else lo = mid + 1; } return lo; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...