Submission #414715

#	Time	Username	Problem	Language	Result	Execution time	Memory
414715		blue	Robots (IOI13_robots)	C++17	90 / 100	221 ms	65540 KiB

robots

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

int ceil_div(int a, int b)
{
    return a/b + ((a%b) ? 1 : 0);
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    sort(X, X+A, [] (int x, int y)
    {
        return x > y;
    });

    sort(Y, Y+B, [] (int x, int y)
    {
        return x > y;
    });

    int ct[A+1][B+1];
    for(int i = 0; i <= A; i++)
        for(int j = 0; j <= B; j++)
            ct[i][j] = 0;


    for(int j = 0; j < T; j++)
    {
        int bitI = -1;
        for(int b = 18; b >= 0; b--)
        {
            if(bitI + (1 << b) >= A) continue;
            if(X[bitI + (1 << b)] <= W[j]) continue;
            bitI += (1 << b);
        }

        int bitJ = -1;
        for(int b = 18; b >= 0; b--)
        {
            if(bitJ + (1 << b) >= B) continue;
            if(Y[bitJ + (1 << b)] <= S[j]) continue;
            bitJ += (1 << b);
        }

        ct[bitI+1][bitJ+1]++;
    }

    if(ct[0][0]) return -1;

    for(int i = 0; i <= A; i++)
    {
        for(int j = 0; j <= B; j++)
        {
            if(i > 0)
                ct[i][j] += ct[i-1][j];

            if(j > 0)
                ct[i][j] += ct[i][j-1];

            if(i > 0 && j > 0)
                ct[i][j] -= ct[i-1][j-1];
        }
    }



    int res = 0;

    for(int i = 0; i <= A; i++)
    {
        for(int j = 0; j <= B; j++)
        {
            // cerr << ct[i][j] << ' ';
            if(i+j == 0) continue;
            res = max(res, ceil_div(ct[i][j], i+j));
        }
        // cerr << '\n';
    }

    // int sm = 0;
    //
    // if(ct[0]) return -1;
    // for(int i = 1; i <= A; i++)
    // {
    //     sm += ct[i];
    //     res = max(res, sm/i + ((sm%i) ? 1 : 0));
    // }

    return res;
}



//Subtask 2: 1D
/*
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    sort(X, X+A, [] (int x, int y)
    {
        return x > y;
    });

    vector<int> ct(A+1, 0);
    for(int j = 0; j < T; j++)
    {
        int bit = -1; //locate last robot that can handle toy j
        for(int b = 18; b >= 0; b--)
        {
            if(bit + (1 << b) >= A) continue;
            if(X[bit + (1 << b)] <= W[j]) continue;
            bit += (1 << b);
        }
        ct[bit+1]++;
    }

    int res = 0;
    int sm = 0;

    if(ct[0]) return -1;
    for(int i = 1; i <= A; i++)
    {
        sm += ct[i];
        res = max(res, sm/i + ((sm%i) ? 1 : 0));
    }

    return res;
}
*/

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