Submission #547160

#	Time	Username	Problem	Language	Result	Execution time	Memory
547160		blue	Robots (IOI13_robots)	C++17	100 / 100	554 ms	28636 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;
};

void recalibrate(int i, vi& nxt, vi& Acurr, int lim)
{
    if(Acurr[nxt[i]] < lim) return;
    else
    {
        recalibrate(nxt[i], nxt, Acurr, lim);
        nxt[i] = nxt[nxt[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)
    {
        int lim = (lo+hi)/2;

        vi Acurr(1+A, 0);
        vi unused;

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

        int wa = 0;

        for(auto& t : toys)
        {
            int wa = worst_small[t.i];

            if(Acurr[wa] == lim)
            {
                recalibrate(wa, nxt, Acurr, lim);
                wa = nxt[wa];
            }

            // while(wa < A && (X[wa] <= t.w || Acurr[wa] == lim))
            //     wa++;

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

        bool works = 1;

        int wb = 0;

        vi Bcurr(1+B, 0);
        reverse(unused.begin(), unused.end());
        for(int k : unused)
        {
            while(wb < B && (Y[wb] <= k || Bcurr[wb] == lim))
                wb++;

            if(wb == B)
                works = 0;
            else
                Bcurr[wb]++;
        }

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

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

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:84:13: warning: unused variable 'wa' [-Wunused-variable]
   84 |         int wa = 0;
      |             ^~

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