Submission #547153

#	Time	Username	Problem	Language	Result	Execution time	Memory
547153		blue	Robots (IOI13_robots)	C++17	14 / 100	325 ms	16264 KiB

robots

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

using pii = pair<int, int>;
using vi = vector<int>;

struct toy
{
    int w;
    int s;
    int i;
};


      //weak #, small #, toys #, weight lim, size lim, toy weight, toy size
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    swap(A, B);
    swap(X, Y);
    swap(W, S);

    sort(X, X+A);
    sort(Y, Y+B);

    vector<toy> toys(T);
    // cerr << "done\n";
    for(int t = 0; t < T; t++) 
    {
        // cerr << 
        toys[t] = {W[t], S[t], t};
    // cerr << "done : " << t << '\n';
    }


    sort(toys.begin(), toys.end(), [] (toy u, toy v)
    {
        return u.w < v.w;
    });

    vi worst_small(T, A);
    int it = -1;
    for(int a = 0; a < A; a++)
    {
        while(it+1 < T && toys[it+1].w < X[a])
        {
            it++;
            worst_small[toys[it].i] = a;
        }
    }

    sort(toys.begin(), toys.end(), [] (toy u, toy v)
    {
        return u.s > v.s;
    });

    // cerr << "done\n";


    int lo = 1, hi = T+1;
    while(lo != hi)
    {
        // cerr << lo << ' ' << hi << '\n';
        int lim = (lo+hi)/2;

        vi unused;

        vi nxt(A+1);
        for(int a = 0; a < A; a++)
            nxt[a] = a+1;
        nxt[A] = A;

        vi Acurr(A+1, 0);

        // cerr << "A = " << A << '\n';

        for(auto& t : toys)
        {
            int ws = worst_small[t.i];
            while(Acurr[nxt[ws]] == lim)
            {
                // cerr << nxt[ws] << ' ' << Acurr[nxt[ws]] << '\n';
                nxt[ws] = nxt[nxt[ws]];
            }
            if(Acurr[ws] == lim)
                ws = nxt[ws];

            if(ws == A)
                unused.push_back(t.s);
            else
            {
                Acurr[ws]++;
            }
        }

        // cerr << "done\n";


        vi Bcurr(B+1, 0);

        int bi = 0;

        bool works = 1;

        for(int k : unused)
        {
            if(Bcurr[bi] == lim) bi++;
            if(bi == B)
            {
                works = 0;
                break;
            }
            while(bi < B && Y[bi] <= k)
                bi++;

            if(bi == B)
            {
                works = 0;
                break;
            }

            Bcurr[bi]++;
        }

        if(works)
            hi = lim;
        else
            lo = lim+1;

    }

    if(lo == T+1) return -1;
    else return lo;
}

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