제출 #962661

#제출 시각아이디문제언어결과실행 시간메모리
962661NValchanov로봇 (IOI13_robots)C++17
0 / 100
2 ms8540 KiB
#include <bits/stdc++.h> #include "robots.h" using namespace std; typedef long long ll; const ll MAXT = 1e6 + 10; const ll MAXA = 5e4 + 10; const ll MAXB = 5e4 + 10; struct toy { ll sz; ll w; toy(){}; toy(ll _w, ll _sz) { w = _w; sz = _sz; } bool operator<(const toy&t)const { return sz < t.sz; } }; bool cmp(ll a, ll b) { return a > b; } ll t,a,b; ll weak[MAXA]; ll small[MAXB]; toy toys[MAXT]; bool check(ll k) { priority_queue < toy > pq; ll ptr = 0; for(int i = 0; i < b; i++) { while(ptr < t && toys[ptr].sz < small[i]) { pq.push(toys[ptr]); ptr++; } for(int j = 1; j <= k; j++) { if(pq.empty()) break; pq.pop(); } } while(ptr < t) { pq.push(toys[ptr]); ptr++; } for(int i = 0; i < a; i++) { if(pq.empty()) break; if(pq.top().w >= weak[i]) return false; for(int j = 1; j <= k; j++) { if(pq.empty()) break; pq.pop(); } } return pq.empty(); } int solve() { ll left = -1; ll right = t + 1; ll mid; while(left <= right) { mid = left + (right - left) / 2; if(check(mid)) right = mid - 1; else left = mid + 1; } return right == t + 1 ? -1 : right; } int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { t = T; a = A; b = B; for(int i = 0; i < t; i++) { toys[i] = toy(W[i], S[i]); } for(int i = 0; i < a; i++) { weak[i] = X[i]; } for(int i = 0; i < b; i++) { small[i] = Y[i]; } sort(toys, toys + t); sort(weak, weak + a, cmp); sort(small, small + b); return solve(); }
#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...