Submission #402650

#	Time	Username	Problem	Language	Result	Execution time	Memory
402650		prvocislo	Robots (IOI13_robots)	C++17	76 / 100	3069 ms	23824 KiB

robots

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

struct toy { int w, s, id; };
bool cmp(const toy& a, const toy& b)
{
    return a.s > b.s;
}
bool check(vector<int>& x, vector<int>& y, vector<toy>& v, int t)
// predpokladame ze y su striedene tak, ze prvy je ten najvacsi
{
    set<pair<int, int> > m; // vaha ktoru viem zdvihnut, index
    for (int i = 0; i < x.size(); i++) m.insert({ x[i], i });
    vector<int> fx(x.size(), t), fy(y.size(), t);
    int iy = 0;
    for (int i = 0; i < v.size(); i++) // predpokladame ze hracky su striedene tym komparatorom vyssie
    {
        auto it = m.lower_bound({ v[i].w + 1, -1 });
        if (it == m.end())
        {
            while (iy < y.size() && fy[iy] == 0) iy++;
            if (iy == y.size() || y[iy] <= v[i].s) return false;
            fy[iy]--;
        }
        else
        {
            fx[it->second]--;
            if (!fx[it->second]) m.erase(it);
        }
    }
    return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    vector<int> x, y; vector<toy> v;
    for (int i = 0; i < A; i++) x.push_back(X[i]);
    for (int i = 0; i < B; i++) y.push_back(Y[i]);
    sort(y.begin(), y.end(), greater<int>());
    for (int i = 0; i < T; i++) v.push_back({ W[i], S[i], i });
    sort(v.begin(), v.end(), cmp);
    int lo = 1, hi = T + 1;
    while (lo < hi)
    {
        int mid = (lo + hi) >> 1;
        if (check(x, y, v, mid)) hi = mid;
        else lo = mid + 1;
    }
    return (lo > T ? -1 : lo);
}

Compilation message (stderr)

robots.cpp: In function 'bool check(std::vector<int>&, std::vector<int>&, std::vector<toy>&, int)':
robots.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < x.size(); i++) m.insert({ x[i], i });
      |                     ~~^~~~~~~~~~
robots.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < v.size(); i++) // predpokladame ze hracky su striedene tym komparatorom vyssie
      |                     ~~^~~~~~~~~~
robots.cpp:25:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |             while (iy < y.size() && fy[iy] == 0) iy++;
      |                    ~~~^~~~~~~~~~
robots.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             if (iy == y.size() || y[iy] <= v[i].s) return false;
      |                 ~~~^~~~~~~~~~~

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