Submission #1008560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008560		jer033	Robots (IOI13_robots)	C++17	0 / 100	1 ms	600 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int binsearch(int target, vector<int> (&arr))
{
    int lo = 0;
    int hi = arr.size()-1;
    if (hi==-1)
        return 0;
    if (target>arr[hi])
        return hi+1;
    while (lo!=hi)
    {
        int mid = (lo+hi)/2;
        if (arr[mid]>=target)
            hi = mid;
        else
            lo = mid+1;
    }
    return lo;
}

int cel(int a, int b)//ceiling division
{
    if (a==0)
        return 0;
    return ((a-1)/b)+1;
}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    sort(X, X+A);
    sort(Y, Y+B);
    vector<int> x;
    vector<int> y;
    x.reserve(A);
    y.reserve(B);
    for (int i=0; i<A; i++)
        x.push_back(X[i]);
    for (int i=0; i<B; i++)
        y.push_back(Y[i]);
    
    vector<vector<int>> matrix(A+1, vector<int> (B+1, 0));
    for (int i=0; i<T; i++)
    {
        int r = binsearch(W[i], x);
        int c = binsearch(S[i], y);
        matrix[r][c]++;
    }

    for (int i=0; i<=A; i++)
        for (int j=0; j<=B; j++)
        {
            if (i!=A)
                matrix[i][j] = matrix[i][j]+matrix[i+1][j];
        }
    for (int i=0; i<=A; i++)
        for (int j=0; j<=B; j++)
        {
            if (j!=B)
                matrix[i][j] = matrix[i][j]+matrix[i][j+1];
        }
    
    if (matrix[A][B])
        return -1;
    int time = 0;
    for (int i=0; i<=A; i++)
        for (int j=0; j<=B; j++)
            if ((i+j)!=(A+B))
            {
                int time_taken = cel(matrix[i][j], A-i+B-j);
                time = max(time, time_taken);
            }
    return time;
}

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