제출 #578981

#제출 시각아이디문제언어결과실행 시간메모리
578981Mazaalai로봇 (IOI13_robots)C++17
0 / 100
1 ms340 KiB
#include "robots.h" #include <bits/stdc++.h> #define ub upper_bound #define lb lower_bound #define mp make_pair #define ff first #define ss second #define LINE "--------------------\n" using namespace std; using PII = pair <int, int>; int n, m, k, a, b; const int N = 5e4+5; const int M = 1e6+5; int wLimit[N], szLimit[N]; PII toys[M]; bool removed[N]; bool solve(int lim) { priority_queue <int> vals; // cout << LINE; lim = 3; for (int i = a-1, j = n-1; i >= 0 && j >= 0; i--) { while(j >= 0 && toys[j].ff >= wLimit[i]) { vals.push(toys[j].ss); // cout << "SKIP: " << j << ' ' << toys[j].ff << ' ' << toys[j].ss << '\n'; j--; } j -= lim; } for (int i = b-1; i >= 0; i--) { if (!vals.empty() && vals.top() >= szLimit[i]) { // cout << vals.top() << " " << i << ' ' << szLimit[i] << '\n'; return 0; } for (int j = 0; j < lim && !vals.empty(); j++) vals.pop(); } return 1; } int putaway(int weak, int small, int _n, int _wLimit[], int _szLimit[], int _w[], int _sz[]) { n = _n; a = weak; b = small; if (weak > 0) sort(_wLimit, _wLimit+weak); if (small > 0) sort(_szLimit, _szLimit+small); for (int i = 0; i < weak; i++) wLimit[i] = _wLimit[i]; for (int i = 0; i < small; i++) szLimit[i] = _szLimit[i]; for (int i = 0; i < n; i++) toys[i] = {_w[i], _sz[i]}; if (n > 0) sort(toys, toys+n); if (n == 0) return 0; int l = 1, r = n, ans = 1e9; // l = r = 3; while (l <= r) { int mid = (l+r)>>1; if (solve(mid)) { r = mid-1; ans = mid; } else { l = mid+1; } } return ans == 1e9 ? -1 : 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...