Submission #703269

#	Time	Username	Problem	Language	Result	Execution time	Memory
703269		speedyArda	Robots (IOI13_robots)	C++11	100 / 100	1412 ms	12648 KiB

robots

#include "robots.h"
#include "bits/stdc++.h"
using namespace std;
// Sol O(nlog(n)^2) -> Binary search the time. Then first iterate through weak robots in nondecreasing power and when we come to a weak robot, take toys whose weight is smaller than our current weak robot but bigger than our previous weaker weak robot.
//While getting these toys, add their sizes in non-increasing set, and at every weak robot, try to remove minutes amount toy with biggest sizes possible. This is optimal because we will give short robots some toys with less sizes as possible which means more short robots would be able to handle it.
//After iterating through the weak robots, add the remaining toys whose weight are higher than or equal to our strongest weak robot's power. Now for the rest of the toys, by iterating through the biggest sizes toys, try to remvove all toys, iterating through the biggest short robot to smallest.
//For implementation, I used priority_queue as it's faster than multiset and we only the greatest element in our every move from the priority queue.
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    
    sort(X, X + A);
    sort(Y, Y + B);
    int ans = 1e9;
    vector< pair<int, int> > sorted;
    for(int i = 0; i < T; i++)
    {
        sorted.push_back({W[i], S[i]});
    }
    sort(sorted.begin(), sorted.end());
    //reverse(sorted.begin(), sorted.end());
    int l = 1, r = T;
    //cout << "hm\n";
    while(l <= r)
    {
        int m = (l + r) / 2;
        //cout << m << "\n";
        //unordered_set<int, greater<int> > curr;
        priority_queue<int> curr;
        int idx = 0;
        for(int i = 0; i < A; i++)
        {
            while(idx < T && sorted[idx].first < X[i]) {
                curr.push(sorted[idx].second);
                idx++;
            }
            int cnt = 0;
            while(cnt < m && !curr.empty())
            {
                curr.pop();
                cnt++;
            }
        }
        while(idx < T) // Elements whose weights are higher than our strongest weak robot.
        {
            curr.push(sorted[idx].second);
            idx++;
        }
        for(int i = B - 1; i >= 0; i--)
        {
            int cnt = 0;
            while(cnt < m && !curr.empty() && Y[i] > (curr.top()))
            {
                curr.pop();
                cnt++;
            }
        }

        if(curr.size() == 0)
        {
            ans = m;
            r = m - 1;
        } else
            l = m + 1;
    }

    if(ans == 1e9)
        ans = -1;
    return ans;
    //return 42;
}

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