Submission #547156

#	Time	Username	Problem	Language	Result	Execution time	Memory
547156		blue	로봇 (IOI13_robots)	C++17	14 / 100	3075 ms	12548 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)
    {
        // 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 = 0;
            // if(Acurr[ws] == lim)
            // {
            //     // recalibrate(ws, nxt, Acurr, lim);
            //     // ws = nxt[ws];
            // }
            while(ws < A && (Acurr[ws] == lim || X[ws] <= t.w))
                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)
        {
            while(bi < B && (Y[bi] <= k || Bcurr[bi] == lim))
                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