Submission #466668

#	Time	Username	Problem	Language	Result	Execution time	Memory
466668		blue	Robots (IOI13_robots)	C++17	76 / 100	921 ms	65540 KiB

robots

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


int A; //# weak robots

int B; //# small robots

int T; //# toys
int* W1;
int* S1;

struct toyW
{
    int k;
};

bool operator < (toyW P, toyW Q)
{
    if(W1[P.k] == W1[Q.k]) return P.k < Q.k;
    return W1[P.k] < W1[Q.k];
}

struct toyS
{
    int k;
};

bool operator < (toyS P, toyS Q)
{
    if(S1[P.k] == S1[Q.k]) return P.k < Q.k;
    return S1[P.k] < S1[Q.k];
}
set<toyW> TW_1;
set<toyW> TW1, TW2;
set<toyS> TS1, TS2;

int binary_search(int a, int b, int X[], int Y[], int W[], int S[])
{
    if(a == b) return a;

    TS1.clear();

    TW1 = TW_1;
    for(int k = 0; k < T; k++)
    {
        TS1.insert(toyS{k});
    }
    TW2.clear();
    TS2.clear();

    // cerr << "searching range " << a << ' ' << b << '\n';

    int m = (a+b)/2; //The maximum capacity of any robot.

    // for(int x: X) //weak robots
    for(int q = 0; q < A; q++) {int x = X[q];
        // cerr << "x = " << x << '\n';
        while(!TW1.empty() && W[TW1.begin()->k] < x)
        {
            int k = TW1.begin()->k;

            TW1.erase(toyW{k});
            TS1.erase(toyS{k});

            TW2.insert(toyW{k});
            TS2.insert(toyS{k});
        }
        int ctr = 0;
        while(!TS2.empty() && ctr < m)
        {
            ctr++;
            int k = TS2.rbegin()->k;
            TS2.erase(toyS{k});
            TW2.erase(toyW{k});
        }
    }
    while(!TW1.empty())
    {
        int k = TW1.rbegin()->k;

        TW1.erase(toyW{k});
        TS1.erase(toyS{k});

        TW2.insert(toyW{k});
        TS2.insert(toyS{k});
    }

    for(int z = 0; z < B; z++) {int y = Y[z]; //small robots
        // cerr << "y = " << y << '\n';
        int ctr = 0;
        while(!TS2.empty() && S[TS2.begin()->k] < y && ctr < m)
        {
            ctr++;
            TS2.erase(TS2.begin());
        }
    }

    if(!TS2.empty())
        return binary_search(m+1, b, X, Y, W, S);
    else
        return binary_search(a, m, X, Y, W, S);
}


int putaway(int a, int b, int t, int X[], int Y[], int W[], int S[])
{

    A = a;
    sort(X, X+A, [] (int u, int v)
    {
        return u < v;
    });

    // cerr << "check\n";


    B = b;
    sort(Y, Y+B, [] (int u, int v)
    {
        return u < v;
    });
    // cerr << "check\n";


    T = t;
    W1 = &W[0];
    S1 = &S[0];
    for(int k = 0; k < T; k++)
    {
        if((A == 0 || W[k] >= X[A-1]) && (B == 0|| S[k] >= Y[B-1]))
            return -1;

        TW_1.insert(toyW{k});
    }
    // cerr << "checking\n";
    // cerr << "check\n";

    return binary_search(1, T, X, Y, W, S);
}

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