Submission #284512

#	Time	Username	Problem	Language	Result	Execution time	Memory
284512		alexandra_udristoiu	Robots (IOI13_robots)	C++14	100 / 100	1848 ms	22264 KiB

robots

#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;
        u++;
    }
    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;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10