Submission #963976

#	Time	Username	Problem	Language	Result	Execution time	Memory
963976		irmuun	Robots (IOI13_robots)	C++17	76 / 100	3093 ms	35780 KiB

robots

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

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int putaway(int A,int B,int T,int X[],int Y[],int W[],int S[]){
    pair<int,int>toy[T];
    for(int i=0;i<T;i++){
        toy[i].ff=W[i];
        toy[i].ss=S[i];
    }
    sort(toy,toy+T);
    sort(X,X+A);
    sort(Y,Y+B);
    int l=1,r=T+1;
    vector<bool>used(T);
    while(l<r){
        int mid=(l+r)/2;
        fill(all(used),0);
        set<pair<int,int>,greater<pair<int,int>>>st;
        int le=0;
        for(int i=0;i<A;i++){
            while(le<T&&toy[le].ff<X[i]){
                st.insert({toy[le].ss,le});
                le++;
            }
            int cur=mid;
            while(cur--&&!st.empty()){
                used[st.begin()->ss]=true;
                st.erase(st.begin());
            }
        }
        st.clear();
        for(int i=0;i<T;i++){
            if(!used[i]){
                st.insert({toy[i].ss,i});
            }
        }
        for(int i=B-1;i>=0;i--){
            int cur=mid;
            while(cur--&&!st.empty()){
                if(st.begin()->ff<Y[i]){
                    st.erase(st.begin());
                }
                else break;
            }
        }
        if(!st.empty()) l=mid+1;
        else r=mid;
    }
    if(l==T+1) return -1;
    return l;
}

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