Submission #547133

#	Time	Username	Problem	Language	Result	Execution time	Memory
547133		blue	Robots (IOI13_robots)	C++17	76 / 100	3082 ms	24740 KiB

robots

#include "robots.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

using pii = pair<int, int>;
 
      //weak #, small #, toys #, weight lim, size lim, weight, size
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    sort(X, X+A);
    sort(Y, Y+B);

    pii obj[T];
    for(int t = 0; t < T; t++)
        obj[t] = pii{W[t], S[t]};
    sort(obj, obj+T);

    int lo = 1, hi = T;
    while(1)
    {
        int mid = (lo+hi)/2;

        multiset<int> sizes;

        // cerr << lo << ' ' << hi << '\n';


        int it = -1;

        for(int a = 0; a < A; a++)
        {
            while(it+1 < T && obj[it+1].first < X[a])
            {
                it++;
                sizes.insert(obj[it].second);
            }

            for(int z = 1; z <= mid && !sizes.empty(); z++)
            {
                sizes.erase(sizes.find(*sizes.rbegin()));
            }
        }

        while(it+1 < T)
        {
            it++;
            sizes.insert(obj[it].second);
        }



        for(int b = 0; b < B; b++)
        {
            for(int z = 1; z <= mid && !sizes.empty(); z++)
            {
                if(*sizes.begin() >= Y[b])
                    break;

                sizes.erase(sizes.begin());
            }
        }

        if(lo == hi)
        {
            if(sizes.empty())
                return lo;
            else
                return -1;
        }

        if(sizes.empty())
            hi = mid;
        else
            lo = mid+1;
    }
}

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