Submission #547104

#	Time	Username	Problem	Language	Result	Execution time	Memory
547104		blue	Robots (IOI13_robots)	C++17	76 / 100	3037 ms	62160 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;
set<toyS> TS2;
 
// int binary_search(int a, int b, int X[], int Y[], int W[], int 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";

    int lo = 1;
    int hi = T;
    while(1)
    {
        if(lo == hi) return lo;
 
        TW1 = TW_1;
        TS2.clear();
     
        // cerr << "searching range " << a << ' ' << b << '\n';
     
        int m = (lo+hi)/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});
                TS2.insert(toyS{k});
            }
            int ctr = 0;
            while(!TS2.empty() && ctr < m)
            {
                ctr++;
                int k = TS2.rbegin()->k;
                TS2.erase(toyS{k});
            }
        }
        while(!TW1.empty())
        {
            int k = TW1.rbegin()->k;
     
            TW1.erase(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())
            lo = m+1;
        else
            hi = m;
    }
}

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