Submission #113786

#	Time	Username	Problem	Language	Result	Execution time	Memory
113786		Mercenary	Robots (IOI13_robots)	C++14	100 / 100	1728 ms	24644 KiB

robots

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

using namespace std;
typedef pair<int,int> ii;
const int maxn = 1e6 + 6;

int putaway(int n , int m , int k , int a[], int b[], int w[], int s[]) {
    vector<ii> object(k);
    for(int i = 0 ; i < k ; ++i)object[i] = make_pair(w[i] , s[i]);
    int l = 1 , h = k;
    sort(a , a + n);
    sort(b , b + m);
    sort(object.begin(),object.end());
    while(l <= h){
        int mid = l + h >> 1;
        priority_queue<int> pq;
        auto it = object.begin();
        #define ris (*it)
        for(int i = 0 ; i < n ; ++i){
            while(it != object.end() && ris.first < a[i]){
                pq.push(ris.second);
                ++it;
            }
            for(int t = mid ; t-- && !pq.empty() ; pq.pop());
        }
        while(it != object.end())pq.push(ris.second) , ++it;
        for(int i = m - 1 ; i >= 0 ; --i){
            for(int t = mid ; t-- && !pq.empty() && b[i] > pq.top() ; pq.pop());
        }
        if(pq.empty()){
            h = mid - 1;
        }else l = mid + 1;
    }
    return l > k ? -1 : l;
}

Compilation message (stderr)

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

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