제출 #284499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
284499		alexandra_udristoiu	로봇 (IOI13_robots)	C++14	76 / 100	3085 ms	35652 KiB

robots

#include "robots.h"
#include<algorithm>
#include<set>
using namespace std;
static multiset<int> s;
static multiset<int> :: iterator it;
static pair<int, int> p[1000005];
static int w[1000005];
static int verif(int k, int n, int a, int b, int va[], int vb[]){
    int i, j, u, nr;
    u = 0;
    for(i = 0; i < a; i++){
        while(u < n && p[u].first < va[i]){
            s.insert(-p[u].second);
            u++;
        }
        for(j = 1; j <= k; j++){
            if(s.empty()){
                break;
            }
            s.erase( s.begin() );
        }
    }
    while(u < n){
        s.insert(-p[u].second);
        u++;
    }
    nr = 0;
    for(it = s.begin(); it != s.end(); it++){
        w[++nr] = - *it;
    }
    s.clear();
    u = nr;
    for(i = 0; i < b; i++){
        for(j = 1; j <= k; j++){
            if(u == 0 || w[u] >= vb[i]){
                break;
            }
            u--;
        }
    }
    if(u != 0){
        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: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10