Submission #367777

#	Time	Username	Problem	Language	Result	Execution time	Memory
367777		idk321	Robots (IOI13_robots)	C++11	100 / 100	1909 ms	24824 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;
    priority_queue<int> sett;
    for (int i = 0; i < a; i++)
    {
        while (cur < toys.size() && toys[cur][0] < x[i])
        {
            sett.push(toys[cur][1]);
            cur++;
        }

        for (int j = 0; j < t; j++)
        {
            if (sett.empty()) break;
            sett.pop();
        }
    }

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

    for (int i = b - 1; i >= 0; i--)
    {
        for (int j = 0; j < t; j++)
        {
            if (sett.empty()) return true;
            if (y[i] <= sett.top()) return false;
            sett.pop();
        }
    }

    if (sett.empty()) return true;
    return false;
}

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(toys.begin(), toys.end());
    sort(x, x + a);
    sort(y, y + b);


    return bs();
}

Compilation message (stderr)

robots.cpp: In function 'bool poss(int)':
robots.cpp:21: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]
   21 |         while (cur < toys.size() && toys[cur][0] < x[i])
      |                ~~~~^~~~~~~~~~~~~
robots.cpp:34: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]
   34 |     while (cur < toys.size())
      |            ~~~~^~~~~~~~~~~~~
robots.cpp:39:9: warning: unused variable 't2' [-Wunused-variable]
   39 |     int t2 = 0;
      |         ^~

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