제출 #211677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
211677		anonymous	로봇 (IOI13_robots)	C++14	100 / 100	1785 ms	22892 KiB

robots

#include "robots.h"
#include<queue>
#include<utility>
#include<algorithm>
#define MAXT 1000005
#define MAXR 50005
using namespace std;
pair<int,int> Toy[MAXT];
priority_queue<int> PQ; //from big to small
int A, B, T, Weak[MAXR], Small[MAXR]; //weak size, small size
bool can(int k) {
    int pt = 0;
    while (PQ.size()) {PQ.pop();}
    for (int i=0; i<A; i++) {
        while (pt < T && Toy[pt].first < Weak[i]) {
            PQ.push(Toy[pt].second), pt++;
        }
        for (int j=0; j<k && PQ.size(); j++) {PQ.pop();}
    }
    for (int i=pt; i<T; i++) {
        PQ.push(Toy[i].second);
    }
    for (int i=B-1; i>=0; i--) {
        for (int j=0; j<k; j++) {
            if (PQ.size() && PQ.top() < Small[i]) {PQ.pop();}
            else {break;}
        }
    }
    return(PQ.empty());
}

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
    A=a, B=b, T=t; //weak num, small num, toy num
    for (int i=0; i<T; i++) {
        Toy[i].first = w[i];
        Toy[i].second = 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(Weak, Weak+A);
    sort(Small, Small+B);
    sort(Toy, Toy+T);
    for (int i=0; i<T; i++) {
        if ((!A || Toy[i].first >= Weak[A-1]) && (!B || Toy[i].second >= Small[B-1])) {
            return(-1);
        }
    }
    int lo = 0, hi = T;
    while (lo + 1 != hi) {
        int mid = (lo + hi) >> 1;
        if (can(mid)) {hi = mid;}
        else {lo = mid;}
    }
    return(hi);
}

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