Submission #1036331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036331		DeathIsAwe	Robots (IOI13_robots)	C++14	100 / 100	1208 ms	26020 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;
#define ll long long

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
    vector<int> rw, rs;
    for (int i=0;i<a;i++) {
        rw.push_back(x[i]);
    }
    for (int i=0;i<b;i++) {
        rs.push_back(y[i]);
    }
    sort(rw.begin(), rw.end());
    sort(rs.begin(), rs.end());
    vector<pair<int,int>> toys;
    for (int i=0;i<t;i++) {
        toys.push_back(make_pair(w[i],s[i]));
    }
    sort(toys.begin(), toys.end());



    priority_queue<int> maxpq;
    vector<int> sizes;
    int top = t + 1, bottom = 0, middle;
    int tracker=0;
    while (bottom + 1 < top) {
        middle = (top + bottom)/2;
        sizes.clear();
        for (int i=0;i<a;i++) {
            while (toys[tracker].first < rw[i] && tracker < t) {
                maxpq.push(toys[tracker++].second);
            }
            for (int j=0;j<middle;j++) {
                if (maxpq.empty()) {
                    break;
                }
                maxpq.pop();
            }
        }
        while (!maxpq.empty()) {
            sizes.push_back(maxpq.top());
            maxpq.pop();
        }
        for (int i=tracker;i<t;i++) {
            sizes.push_back(toys[i].second);
        }
        sort(sizes.begin(), sizes.end(), greater<int>());
        tracker = 0;
        for (int i=0;i<b;i++) {
            for (int j=0;j<middle;j++) {
                if (sizes.empty()) {
                    break;
                }
                if (sizes[sizes.size()-1] >= rs[i]) {
                    break;
                }
                sizes.pop_back();
            }
        }
        if (sizes.empty()) {
            top = middle;
        } else {
            bottom = middle;
        }
    }
    if (top == t + 1) {
        return -1;
    } else {
        return top;
    }
}

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