Submission #1008593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008593		jer033	Robots (IOI13_robots)	C++17	90 / 100	174 ms	65536 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);
        //cout << "toy at row " << r << '\n';
        matrix[r][c]++;
    }
    //cout << matrix[0][0] << matrix[1][0] << matrix[2][0] << matrix[3][0] << " balala\n";

    for (int i=A; i>=0; i--)
        for (int j=B; j>=0; j--)
        {
            if (i!=A)
                matrix[i][j] = matrix[i][j]+matrix[i+1][j];
        }
    for (int i=A; i>=0; i--)
        for (int j=B; j>=0; j--)
        {
            if (j!=B)
                matrix[i][j] = matrix[i][j]+matrix[i][j+1];
        }
    
    //cout << "bad robot count: " << matrix[A][B] << '\n';
    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);
                //cout << "row i contains " << matrix[i][j] << " toys, cumulatively and it takes " << time_taken << '\n';
                time = max(time, time_taken);
            }
    return time;
}

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