Submission #402659

#	Time	Username	Problem	Language	Result	Execution time	Memory
402659		prvocislo	Robots (IOI13_robots)	C++17	100 / 100	473 ms	23228 KiB

robots

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

struct toy { int xi, s, id; };
bool cmp(const toy& a, const toy& b)
{
    return a.s > b.s;
}
vector<int> p; 
int root(int x) { return x == p[x] ? x : p[x] = root(p[x]); }
void merge(int x, int y)
{
    x = root(x), y = root(y);
    p[x] = y;
}
bool check(vector<int>& x, vector<int>& y, vector<toy>& v, int t)
// predpokladame ze y su striedene tak, ze prvy je ten najvacsi
{
    vector<int> fx(x.size(), t), fy(y.size(), t);
    p.assign(x.size() + 1, 0);
    for (int i = 0; i <= x.size(); i++) p[i] = i;
    int iy = 0;
    for (int i = 0; i < v.size(); i++) // predpokladame ze hracky su striedene tym komparatorom vyssie
    {
        int it = root(v[i].xi);
        if (it == x.size())
        {
            while (iy < y.size() && fy[iy] == 0) iy++;
            if (iy == y.size() || y[iy] <= v[i].s) return false;
            fy[iy]--;
        }
        else
        {
            fx[it]--;
            if (!fx[it]) merge(it, it + 1);
        }
    }
    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]);
    sort(x.begin(), x.end());
    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({ lower_bound(x.begin(), x.end(), W[i] + 1) - x.begin(), 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:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 0; i <= x.size(); i++) p[i] = i;
      |                     ~~^~~~~~~~~~~
robots.cpp:26:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<toy>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for (int i = 0; i < v.size(); i++) // predpokladame ze hracky su striedene tym komparatorom vyssie
      |                     ~~^~~~~~~~~~
robots.cpp:29:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         if (it == x.size())
      |             ~~~^~~~~~~~~~~
robots.cpp:31:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |             while (iy < y.size() && fy[iy] == 0) iy++;
      |                    ~~~^~~~~~~~~~
robots.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |             if (iy == y.size() || y[iy] <= v[i].s) return false;
      |                 ~~~^~~~~~~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:49:89: warning: narrowing conversion of '__gnu_cxx::operator-<int*, std::vector<int> >(std::lower_bound<__gnu_cxx::__normal_iterator<int*, std::vector<int> >, int>(x.std::vector<int>::begin(), x.std::vector<int>::end(), ((*(W + ((sizetype)(((long unsigned int)i) * 4)))) + 1)), x.std::vector<int>::begin())' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' [-Wnarrowing]
   49 |     for (int i = 0; i < T; i++) v.push_back({ lower_bound(x.begin(), x.end(), W[i] + 1) - x.begin(), S[i], i });
      |                                               ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

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