제출 #1026427

#제출 시각아이디문제언어결과실행 시간메모리
1026427onbert로봇 (IOI13_robots)C++17
76 / 100
632 ms65536 KiB
#include "robots.h" #include <bits/stdc++.h> using namespace std; #define int long long struct toy { int w, s, id; bool operator < (const toy &b) const { if (w!=b.w) return w < b.w; if (s!=b.s) return s < b.s; return id < b.id; } }; struct thing { int w, s, id; bool operator < (const thing &b) const { return s < b.s; } }; int32_t putaway(int32_t n, int32_t m, int32_t k, int32_t x[], int32_t y[], int32_t W[], int32_t S[]) { sort(x, x+n); sort(y, y+m); int mxw = 0, mxs = 0; if (n > 0) mxw = x[n-1]; if (m > 0) mxs = y[m-1]; toy a[2][k]; for (int i=0;i<k;i++) { a[0][i] = {W[i], S[i], -1}; a[1][i] = {S[i], W[i], -1}; if (W[i] >= mxw && S[i] >= mxs) return -1; } sort(a[0], a[0]+k); sort(a[1], a[1]+k); for (int i=0;i<k;i++) a[1][i].id = i; set<toy> s; for (int i=0;i<k;i++) s.insert(a[1][i]); for (int i=0;i<k;i++) { toy bnd = {a[0][i].s, a[0][i].w, -1}; toy cur = *s.lower_bound(bnd); a[0][i].id = cur.id; s.erase(cur); } int l = 1, r = k; while (l<r) { int each = (l+r)/2; bool used[k]; for (int i=0;i<k;i++) used[i] = false; priority_queue<thing> pq; int pt = -1; for (int i=0;i<n;i++) { int lim = x[i]; while (pt<k-1 && a[0][pt+1].w < lim) { pt++; pq.push({a[0][pt].w, a[0][pt].s, a[0][pt].id}); // cout << "add " << lim << " " << a[0][pt].w << " " << a[0][pt].s << endl; } for (int j=0;j<each;j++) { if (pq.size()==0) break; thing cur = pq.top(); used[cur.id] = true; // cout << lim << " " << cur.w << " " << cur.s << endl; pq.pop(); } } pt = -1; for (int i=0;i<m;i++) { int lim = y[i]; int cnt = 0; while (cnt<each && pt<k-1 && a[1][pt+1].w<lim) { pt++; if (!used[pt]) cnt++; used[pt] = true; } } bool ok = true; for (int i=0;i<k;i++) if (!used[i]) ok = false; if (ok) r = each; else l = each + 1; } return l; }
#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...