Submission #1023534

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023534		boyliguanhan	Robots (IOI13_robots)	C++17	100 / 100	1872 ms	22992 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> stuff;
vector<int>small,weak;
int ok(int tm){
    map<int,int>kriby;
    for(auto y:small)
        kriby[y]+=tm;
    int wk=weak.size()-1;
    for(auto[w,s]:stuff){
        if(~wk&&w<weak[wk])
            kriby[2e9+1]+=tm,wk--;
        auto use=kriby.upper_bound(s);
        if(use==kriby.end())return 0;
        use->second--;
        if(!use->second)
            kriby.erase(use);
    }
    return 1;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    for(int i=0;i<A;i++)
        weak.push_back(X[i]);
    for(int i=0;i<B;i++)
        small.push_back(Y[i]);
    for(int i=0;i<T;i++)
        stuff.push_back({W[i],S[i]});
    sort(stuff.rbegin(),stuff.rend());
    sort(small.begin(),small.end());
    sort(weak.begin(),weak.end());
    int l=1,r=T,res=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(ok(mid))
            res=mid,r=mid-1;
        else l=mid+1;
    }
    return res;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:34:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         int mid=l+r>>1;
      |                 ~^~

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