Submission #466591

#	Time	Username	Problem	Language	Result	Execution time	Memory
466591		blue	Robots (IOI13_robots)	C++17	Compilation error	0 ms	0 KiB

robots

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


int A; //# weak robots
vector<int> X;

int B; //# small robots
vector<int> Y;

int T; //# toys
vector<int> W;
vector<int> S;

struct toyW
{
    int k;
};

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

struct toyS
{
    int k;
};

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

int binary_search(int a, int b)
{
    if(a == b) return a;

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

    int m = (a+b)/2; //The maximum capacity of any robot.
    set<toyW> TW1;
    set<toyS> TS1;
    for(int k = 0; k < T; k++)
    {
        TW1.insert(toyW{k});
        TS1.insert(toyS{k});
    }

    set<toyW> TW2;
    set<toyS> TS2;

    for(int x: X) //weak robots
    {
        // 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 y: Y) //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);
    else
        return binary_search(a, m);
}


int putaway(int a, int b, int t, int x[], int y[], int w[], int s[])
{
    A = a;
    X = vector<int>(A);
    for(int i = 0; i < A; i++) X[i] = x[i];
    sort(X.begin(), X.end(), [] (int u, int v)
    {
        return u < v;
    });

    // cerr << "check\n";


    B = b;
    Y = vector<int>(B);
    for(int j = 0; j < B; j++) Y[j] = y[j];
    sort(Y.begin(), Y.end(), [] (int u, int v)
    {
        return u < v;
    });
    // cerr << "check\n";


    T = t;
    W = S = vector<int>(T);
    for(int k = 0; k < T; k++)
    {
        W[k] = w[k];
        S[k] = s[k];

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

        if(W[k] >= X.back() && S[k] >= Y.back())
            return -1;
    }
    // cerr << "checking\n";
    // cerr << "check\n";

    return binary_search(1, T);
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:118:5: error: 'sort' was not declared in this scope; did you mean 'qsort'?
  118 |     sort(X.begin(), X.end(), [] (int u, int v)
      |     ^~~~
      |     qsort