Submission #898082

#	Time	Username	Problem	Language	Result	Execution time	Memory
898082		Ghulam_Junaid	Robots (IOI13_robots)	C++17	90 / 100	3056 ms	32084 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;

int putaway(int weak, int small, int n, int wei_lim[], int sz_lim[], int w[], int sz[]){

    if (small == 0){
        sort(wei_lim, wei_lim + weak);
        sort(w, w + n);

        if (w[n - 1] >= wei_lim[weak - 1])
            return -1;

        int l = 0;
        int r = n;

        while (r - l > 1){
            int mid = (l + r) / 2;
            bool good = 1;

            int cur_sz = 0;
            int cur_p = weak - 1;
            for (int i = n - 1; i >= 0; i--){
                if (cur_p < 0) {good = 0; break;}

                if (w[i] < wei_lim[cur_p]){
                    cur_sz++;
                    if (cur_sz >= mid){
                        cur_sz = 0;
                        cur_p--;
                    }
                }
                else{
                    good = 0;
                    break;
                }
            }

            if (good)
                r = mid;
            else
                l = mid;
        }

        return r;
    }

    if (weak == 0){
        sort(sz_lim, sz_lim + small);
        sort(sz, sz + n);

        if (sz[n - 1] >= sz_lim[small - 1])
            return -1;

        int l = 0;
        int r = n;

        while (r - l > 1){
            int mid = (l + r) / 2;
            bool good = 1;

            int cur_sz = 0;
            int cur_p = small - 1;
            for (int i = n - 1; i >= 0; i--){
                if (cur_p < 0) {good = 0; break;}

                if (sz[i] < sz_lim[cur_p]){
                    cur_sz++;
                    if (cur_sz >= mid){
                        cur_sz = 0;
                        cur_p--;
                    }
                }
                else{
                    good = 0;
                    break;
                }
            }

            if (good)
                r = mid;
            else
                l = mid;
        }

        return r;
    }

    sort(wei_lim, wei_lim + weak);
    sort(sz_lim, sz_lim + small);

    for (int i=0; i<n; i++)
        if (w[i] >= wei_lim[weak - 1] && sz[i] >= sz_lim[small - 1])
            return -1;

    vector<pair<int, int>> vec(n);
    for (int i=0; i<n; i++)
        vec[i] = {w[i], i};
    sort(vec.begin(), vec.end());

    int l = max(0, n / (weak + small) - 1); 
    int r = n;

    int mid, p1, i, j, ind;

    set<pair<int, int>> st;
    while (r - l > 1){
        mid = (l + r) / 2;

        st.clear();
        p1 = 0;
        for (i=0; i<weak; i++){
            while(p1 < n){
                if (vec[p1].first >= wei_lim[i]){
                    break;
                }
                ind = vec[p1].second;
                st.insert({-sz[ind], ind});
                p1++;
            }

            if (st.size() <= mid) {
                st.clear();
            }
            else{
                for (j=0; j<mid; j++)
                    st.erase(st.begin());
            }
        }

        for (j = p1; j<n; j++){
            ind = vec[j].second;
            st.insert({-sz[ind], ind});
        }

        for (i=small - 1; i>=0; i--){
            for (j = 0; j < mid && !st.empty(); j++){
                ind = (*st.begin()).second;

                if (sz[ind] >= sz_lim[i])
                    break;

                st.erase(st.begin());
            }
        }

        if (!st.empty())
            l = mid;
        else
            r = mid;

    }

    return r;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:122:27: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  122 |             if (st.size() <= mid) {
      |                 ~~~~~~~~~~^~~~~~

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