Submission #395993

#	Time	Username	Problem	Language	Result	Execution time	Memory
395993		phathnv	Robots (IOI13_robots)	C++11	100 / 100	1982 ms	22500 KiB

robots

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

using namespace std;

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
    int ind[t];
    for(int i = 0; i < t; i++)
        ind[i] = i;
    sort(ind, ind + t, [&](const int &a, const int &b){
            return w[a] < w[b];
         });
    sort(x, x + a);
    sort(y, y + b);
    int l = 1, r = t, res = -1;
    while (l <= r){
        int mid = (l + r) >> 1;
        priority_queue<int> pq;
        int ptr = 0;
        for(int i = 0; i < a; i++){
            while (ptr < t && w[ind[ptr]] < x[i])
                pq.push(s[ind[ptr++]]);
            for(int j = 0; j < mid; j++)
                if (!pq.empty())
                    pq.pop();
                else
                    break;
        }
        while (ptr < t){
            pq.push(s[ind[ptr++]]);
        }
        for(int i = b - 1; i >= 0; i--)
            for(int j = 0; j < mid; j++)
                if (!pq.empty() && pq.top() < y[i])
                    pq.pop();
                else
                    break;
        if (pq.empty()){
            res = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return res;
}

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