Submission #898080

#	Time	Username	Problem	Language	Result	Execution time	Memory
898080		Ghulam_Junaid	Robots (IOI13_robots)	C++17	100 / 100	1266 ms	20936 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;
 
    priority_queue<int, vector<int>, greater<int>> st;
    while (r - l > 1){
        mid = (l + r) / 2;
 
        while(!st.empty())
            st.pop();
        p1 = 0;
        for (i=0; i<weak; i++){
            while(p1 < n){
                if (vec[p1].first >= wei_lim[i]){
                    break;
                }
                ind = vec[p1].second;
                st.push(-sz[ind]);
                p1++;
            }
 
            for (j=0; j<mid && !st.empty(); j++)
                st.pop();
        }
 
        for (j = p1; j<n; j++){
            ind = vec[j].second;
            st.push(-sz[ind]);
        }
 
        for (i=small - 1; i>=0; i--){
            for (j = 0; j < mid && !st.empty(); j++){
                int y = -(st.top());
 
                if (y >= sz_lim[i])
                    break;
 
                st.pop();
            }
        }
 
        if (!st.empty())
            l = mid;
        else
            r = mid;
 
    }
 
    return r;
}

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