Submission #1106054

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106054		RKHTM	Robots (IOI13_robots)	C++14	76 / 100	3040 ms	36788 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
#define yasuho ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
typedef long long ll;
const ll MOD = 1e9+7;

int putaway(int a, int b, int t, int x[], int y[], int weight[], int size[]){
    sort(x, x+a);
    sort(y, y+b);

    int mxa=INT_MIN, mxb=INT_MIN;
    for(int i=0; i<a; i++) mxa = max(mxa, x[i]);
    for(int i=0; i<b; i++) mxb = max(mxb, y[i]);
    for(int i=0; i<t; i++){
        if(weight[i]<mxa or size[i]<mxb) continue;
        return -1;
    }

    ll l=1, r=t, m/*time*/;
    while(l<=r){
        m = (l+r)/2;
        // cout << l << ' ' << r << ' ' << m << endl;
        priority_queue<pair<ll, ll>> all; // {-weight, size}
        for(int i=0; i<t; i++) all.push({-1*weight[i], size[i]});
        priority_queue<pair<ll, ll>> in; // {size, weight}
        for(int i=0; i<a; i++){
            while(not all.empty() and all.top().first*-1<x[i]){
                in.push({all.top().second, all.top().first*-1});
                all.pop();
            }
            for(int j=1; j<=m and not in.empty(); j++) in.pop();
        }

        priority_queue<pair<ll, ll>> jackpot; // {-size, weight}
        while(not all.empty()){
            jackpot.push({all.top().second*-1, all.top().first*-1});
            all.pop();
        }
        while(not in.empty()){
            jackpot.push({in.top().first*-1, in.top().second});
            in.pop();
        }
        for(int i=0; i<b; i++){
            for(int j=1; j<=m and not jackpot.empty(); j++){
                if(jackpot.top().first*-1>=y[i]) break;
                jackpot.pop();
            }
        }

        if(jackpot.empty()) r=m-1;
        else l=m+1;
    }

    return l;
}

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