Submission #931279

#	Time	Username	Problem	Language	Result	Execution time	Memory
931279		AlphaMale06	Robots (IOI13_robots)	C++17	76 / 100	3068 ms	36632 KiB

robots

#include<bits/stdc++.h>
#include "robots.h"

#define F first
#define S second
#define pb push_back

using namespace std;

int putaway(int n, int m, int S, int a[], int b[], int w[], int s[]) {
    pair<int, int> p[S];
    for(int i=0; i< S; i++)p[i]={w[i], s[i]};
    sort(p, p+S);
    sort(a, a+n);
    sort(b, b+m);
    for(int i=0; i< n; i++)a[i]--;
    for(int i=0; i< m; i++)b[i]--;
    int ans=1e9;
    int l=0, r = S;
    while(l<=r){
        int s=l+r>>1;
        multiset<int> st;
        int pt=0;
        for(int i=0; i< n; i++){
            while(pt<S && p[pt].F<=a[i]){
                st.insert(p[pt].S);
                pt++;
            }
            if(st.size()<=s){
                st.clear();
                continue;
            }
            for(int j=0; j<s; j++){
                st.erase(st.find((*st.rbegin())));
            }
        }
        while(pt<S){
            st.insert(p[pt].S);
            pt++;
        }
        vector<int> v;
        for(auto p : st)v.pb(p);
        for(int i = m-1; i>=0; i--){
            for(int j=0; j<s; j++){
                if(v.size()){
                    if(v.back()<=b[i]){
                        v.pop_back();
                    }
                    else break;
                }
                else break;
            }
        }
        if(v.size()){
            l=s+1;
        }
        else{
            r=s-1;
            ans=s;
        }
    }
    if(ans==1e9)return -1;
    return ans;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:21:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         int s=l+r>>1;
      |               ~^~
robots.cpp:29:25: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |             if(st.size()<=s){
      |                ~~~~~~~~~^~~

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