Submission #1325320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325320		vicvic	Robots (IOI13_robots)	C++20	100 / 100	1275 ms	8832 KiB

robots

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

int putaway (int n, int m, int t, int x[], int y[], int w[], int s[])
{
    sort (x, x+n), sort (y, y+m);
    vector <int> ind (t, 0);
    for (int i=0;i<t;i++)
        ind[i]=i;
    sort (ind.begin(), ind.end(), [&] (int a, int b) {return w[a]<w[b];});
    int st=1, dr=t+1, poz=t+1;
    priority_queue <int> pq;
    auto check = [&] (int val)
    {
        int nxt=0;
        for (int i=0;i<n;i++)
        {
            while (nxt<t && w[ind[nxt]]<x[i])
                pq.push (s[ind[nxt++]]);
            int remain=val;
            while (!pq.empty() && remain--)
                pq.pop ();
        }
        while (nxt<t)
            pq.push (s[ind[nxt++]]);
        for (int i=m-1;i>=0;i--)
        {
            int remain=val;
            while (remain-- && !pq.empty() && pq.top()<y[i])
                pq.pop ();
        }
        return pq.empty();
    };
    while (st<=dr)
    {
        int mij = (st+dr) >> 1;
        while (!pq.empty())
            pq.pop ();
        if (check (mij))
            dr=mij-1, poz=mij;
        else
            st=mij+1;
    }
    return (poz==t+1?-1:poz);
}

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