Submission #713992

#	Time	Username	Problem	Language	Result	Execution time	Memory
713992		Ahmed57	Robots (IOI13_robots)	C++14	100 / 100	2810 ms	32768 KiB

robots

#include "robots.h"

#include <bits/stdc++.h>

using namespace std;
vector<int> w,s;
bool comp(int a,int b){
    if(w[a]!=w[b])return w[a]>w[b];
    return s[a]>s[b];
}
int putaway(int A,int B,int T,int X[],int Y[],int W[],int S[]){
    sort(X,X+A);
    sort(Y,Y+B);
    vector<int>ind;
    for(int i = 0;i<T;i++){
        ind.push_back(i);s.push_back(S[i]);w.push_back(W[i]);
    }
    sort(ind.begin(),ind.end(),comp);
    int l = 1 , r = 1e6 , ans= -1;
    while(l<=r){
        int mid=(l+r)/2;
        set<pair<int,int>> bb;
        priority_queue<pair<int,int>> pa,aa;
        for(int i = 0;i<B;i++)bb.insert({i,mid});
        int z = A-1;
        pair<int,int> p;p.second = 0;
        bool ss = 1;
        for(int i = 0;i<T;i++){
            int toy = ind[i];
            while(z>=0&&X[z]>W[toy]){
                aa.push({z--,mid});
            }
            int in = lower_bound(Y,Y+B,S[toy]+1)-Y;
            pa.push({-in,toy});
            if(aa.size()){
                pair<int,int>tmp = aa.top();
                aa.pop();
                tmp.second--;
                if(tmp.second){
                    aa.push(tmp);
                }
            }else{
                p.first=-pa.top().first;
                p.second = 0;
                auto it2 = bb.lower_bound(p);
                if(it2==bb.end()){
                    ss= 0;
                    break;
                }
                pair<int,int>tmp=*it2;
                bb.erase(it2);
                tmp.second--;
                if(tmp.second)bb.insert(tmp);
                pa.pop();
            }
        }
        if(ss)r = mid-1, ans= mid;
        else l = mid+1;
    }
    return ans;
}
/*
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int X[] = {6,2,9};
    int Y[] = {4,7};
    int W[] = {4,8,2,7,1,5,3,8,7,10};
    int S[] = {6,5,3,9,8,1,3,7,6,5};
    cout<<putaway(3,2,10,X,Y,W,S)<<endl;
}
*/
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
*/

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