This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "robots.h"
#include<algorithm>
#define DIM 1000005
using namespace std;
static pair<int, int> p[DIM];
static int h[DIM], nr;
static void adauga(int val){
h[++nr] = val;
int c = nr, p = c / 2;
while(p > 0 && h[p] < h[c]){
swap(h[p], h[c]);
c = p;
p = c / 2;
}
}
static void elim(){
int p = 1, c = 2;
swap(h[1], h[nr]);
nr--;
while(c <= nr){
if(c + 1 <= nr && h[c] < h[c + 1]){
c++;
}
if(h[p] < h[c]){
swap(h[p], h[c]);
p = c;
c = 2 * p;
}
else{
break;
}
}
}
static int verif(int k, int n, int a, int b, int va[], int vb[]){
int i, j, u;
u = nr = 0;
for(i = 0; i < a; i++){
while(u < n && p[u].first < va[i]){
adauga(p[u].second);
u++;
}
for(j = 1; j <= k; j++){
if(nr == 0){
break;
}
elim();
}
}
while(u < n){
h[++nr] = p[u].second;
}
sort(h + 1, h + nr + 1);
u = 1;
for(i = 0; i < b; i++){
for(j = 1; j <= k; j++){
if(u == nr + 1 || h[u] >= vb[i]){
break;
}
u++;
}
}
if(u != nr + 1){
return 0;
}
return 1;
}
int putaway(int a, int b, int n, int va[], int vb[], int wa[], int wb[]) {
int i, st, dr, mid;
sort(va, va + a);
sort(vb, vb + b);
for(i = 0; i < n; i++){
p[i] = make_pair(wa[i], wb[i]);
}
sort(p, p + n);
st = 1;
dr = n;
while(st <= dr){
mid = (st + dr) / 2;
if( verif(mid, n, a, b, va, vb) ){
dr = mid - 1;
}
else{
st = mid + 1;
}
}
if(st == n + 1){
return -1;
}
return st;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |