제출 #370996

#제출 시각아이디문제언어결과실행 시간메모리
370996shivensinha4로봇 (IOI13_robots)C++17
14 / 100
308 ms8704 KiB
#include "bits/stdc++.h" #include"robots.h" #ifdef mlocal #include "grader.c" #endif using namespace std; #define for_(i, s, e) for (int i = s; i < (int) e; i++) #define for__(i, s, e) for (ll i = s; i < e; i++) typedef long long ll; typedef vector<int> vi; typedef array<int, 2> ii; #define endl '\n' int a, b, t; vi ct; vector<bool> done; vector<ii> toys; struct cmp { bool operator() (const ii &a, const ii &b) const { return a[0] < b[0]; } }; bool check(int box, int wlim[], int slim[]) { done.assign(t, false); ct.assign(b, box); set<ii, cmp> s; int rem = t; for_(i, 0, b) s.insert({slim[i], i}); for_(i, 0, t) { auto pt = s.lower_bound({toys[i][1], -1}); if (pt != s.end()) { done[i] = true; rem--; if (ct[(*pt)[1]] == 1) s.erase(pt); else ct[(*pt)[1]] -= 1; } } int pt = 0, ct; for_(i, 0, a) { ct = 0; while (pt < t and ct < box) { if (!done[pt] and toys[pt][0] <= wlim[i]) { ct++; rem--; done[pt] = true; } pt++; } } return !rem; } int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { a = A, b = B, t = T; toys.reserve(T); for_(i, 0, a) X[i] -= 1; for_(i, 0, b) Y[i] -= 1; for_(i, 0, t) toys.push_back({W[i], S[i]}); sort(X, X+a, greater<>()); sort(Y, Y+b, greater<>()); sort(toys.rbegin(), toys.rend()); for_(i, 0, t) if ((a == 0 or toys[i][0] > X[0]) and (b == 0 or toys[i][1] > Y[0])) return -1; int l = 1, r = T+1, ans = r; while (l < r) { int mid = (l+r)/2; bool fin = check(mid, X, Y); if (fin) { ans = r = mid; } else l = mid+1; } return ans; }
#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...