Submission #367767

#	Time	Username	Problem	Language	Result	Execution time	Memory
367767		idk321	Robots (IOI13_robots)	C++11	76 / 100	3094 ms	35752 KiB

robots

#include "robots.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<array<int, 2>> toys;
int a;
int b;
int* x;
int* y;



bool poss(int t)
{
    int cur = 0;
    sort(toys.begin(), toys.end());
    multiset<int> sett;
    for (int i = 0; i < a; i++)
    {
        while (cur < toys.size() && toys[cur][0] < x[i])
        {
            sett.insert(toys[cur][1]);
            cur++;
        }

        for (int j = 0; j < t; j++)
        {
            if (sett.empty()) break;
            auto it = sett.end();
            it--;
            sett.erase(it);
        }
    }

    while (cur < toys.size())
    {
        sett.insert(toys[cur][1]);
        cur++;
    }
    int t2 = 0;

    if (sett.empty()) return true;
    if (b == 0 || y[b - 1] <= *sett.rbegin()) return false;
    while (!sett.empty())
    {
        for (int i = b - 1;  i >= 0; i--)
        {
            auto it = sett.lower_bound(y[i]);
            if (it == sett.begin()) break;
            it--;
            sett.erase(it);
        }
        t2++;
    }

    return t2 <= t;
}

int bs()
{
    int a = 1;
    int b = toys.size();

    int res = -1;
    while (a <= b)
    {
        int mid = (a + b) / 2;
        if (poss(mid))
        {
            res = mid;
            b = mid - 1;
        } else
        {
            a = mid + 1;
        }
    }

    return res;
}

int putaway(int A, int B, int t, int X[], int Y[], int w[], int s[]) {
    a = A;
    b = B;
    toys.resize(t);
    x = X;
    y = Y;
    for (int i = 0; i < t; i++)
    {
        toys[i][0] = w[i];
        toys[i][1] = s[i];
    }

    sort(x, x + a);
    sort(y, y + b);


    return bs();
}

Compilation message (stderr)

robots.cpp: In function 'bool poss(int)':
robots.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         while (cur < toys.size() && toys[cur][0] < x[i])
      |                ~~~~^~~~~~~~~~~~~
robots.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     while (cur < toys.size())
      |            ~~~~^~~~~~~~~~~~~

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