Submission #931283

#	Time	Username	Problem	Language	Result	Execution time	Memory
931283		AlphaMale06	Robots (IOI13_robots)	C++17	100 / 100	1345 ms	26384 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;
        priority_queue<int> st;
        int pt=0;
        for(int i=0; i< n; i++){
            while(pt<S && p[pt].F<=a[i]){
                st.push(p[pt].S);
                pt++;
            }
            int to = min(s, (int)st.size());
            for(int j=0; j<to; j++){
                st.pop();
            }
        }
        while(pt<S){
            st.push(p[pt].S);
            pt++;
        }
        vector<int> v;
        while(st.size()){
            v.pb(st.top());
            st.pop();
        }
        reverse(v.begin(), v.end());
        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;
      |               ~^~

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