Submission #1276344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276344		k12_khoi	Robots (IOI13_robots)	C++17	14 / 100	1210 ms	10540 KiB

robots

#include "robots.h"

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+5;

int n,m,request,a[N],b[N],W[N],S[N],new_S[N],id[N];
priority_queue<int,vector<int>,less<int>> pq;

bool cmp_W(int x,int y)
{
    return W[x]<W[y];
}

int putaway(int n,int m,int request,int a[],int b[],int W[],int S[])
{
    sort(a,a+n);
    sort(b,b+m);

    for (int i=0;i<request;i++)
    id[i]=i;

    sort(id,id+request,cmp_W);
    sort(W,W+request);

    for (int i=0;i<request;i++)
    new_S[i]=S[id[i]];

    for (int i=0;i<request;i++)
    S[i]=new_S[i];



    auto check = [&](int mid)
    {
        while (!pq.empty()) pq.pop();

        int l=0;
        for (int i=0;i<n;i++)
        {
            while (l<request and W[l]<a[i])
            {
                pq.push(S[l]);
                l++;
            }

            for (int j=1;j<=mid;j++)
            if (pq.empty()) break;
            else pq.pop();
        }

        while (l<request)
        {
            pq.push(S[l]);
            l++;
        }

        for (int i=m-1;i>=0;i--)
        {
            if (pq.empty()) return true;
            if (pq.top()>=b[i]) return false;

            for (int j=1;j<=mid;j++)
            if (pq.empty()) return true;
            else pq.pop();
        }

        return pq.empty();
    };



    int res=-1;
    int l=1;
    int r=request;

    int mid;
    while (l<=r)
    {
        mid=(l+r)/2;
        if (check(mid))
        {
            res=mid;
            r=mid-1;
        }
        else l=mid+1;
    }

    return res;
}

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