제출 #466597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
466597		blue	로봇 (IOI13_robots)	C++17	76 / 100	3099 ms	56204 KiB

robots

#include "robots.h"
#include <vector>
#include <iostream>
#include <algorithm>
#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];
}

set<toyW> T_W1;
set<toyS> T_S1;
set<toyW> TW1, TW2;
set<toyS> TS1, TS2;

int binary_search(int a, int b)
{
    TW1 = T_W1;
    TW2.clear();
    TS1 = T_S1;
    TS2.clear();
    if(a == b) return a;

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

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

    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[])
{
    for(int k = 0; k < T; k++)
    {
        T_W1.insert(toyW{k});
        T_S1.insert(toyS{k});
    }
    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((X.empty() || W[k] >= X.back()) && (Y.empty() || S[k] >= Y.back()))
            return -1;
    }
    // cerr << "checking\n";
    // cerr << "check\n";

    return binary_search(1, T);
}

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