Submission #547161

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

vi parent;
vi subtree;
vi lrg;

int root(int u)
{
    if(u == parent[u]) return u;
    else return (parent[u] = root(parent[u]));
}

void join(int u, int v)
{
    u = root(u);
    v = root(v);
    if(u == v) return;
    if(subtree[u] < subtree[v]) swap(u, v);
    parent[v] = u;
    subtree[u] += subtree[v];
    lrg[u] = max(lrg[u], lrg[v]);
}


      //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";

    parent = subtree = lrg = vi(A+1);


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

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

        for(int i = 0; i <= A; i++)
        {
            parent[i] = lrg[i] = i;
            subtree[i] = 1;
        }

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

            if(wa == A)
                unused.push_back(t.s);
            else
            {
                Acurr[wa]++;
                if(Acurr[wa] == lim)
                    join(wa, wa+1);
            }
        }

        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;
}

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