Submission #813577

#	Time	Username	Problem	Language	Result	Execution time	Memory
813577		TimDee	Robots (IOI13_robots)	C++17	100 / 100	262 ms	11440 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:27: 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:27: 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:20: 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:27: 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:24: 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:93: 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