Submission #92896

#	Time	Username	Problem	Language	Result	Execution time	Memory
92896		stefdasca	Robots (IOI13_robots)	C++14	14 / 100	564 ms	18976 KiB

robots

/*
    We can binary search the answer

    At each step, we will greedily try to assign toys to the weak robots, then to the small robots

    Total complexity will be O(T log T)

*/

#include"robots.h"
#include<bits/stdc++.h>
using namespace std;
bool scos[1000002];
struct str
{
    int qt, b;
    int pi;
};
str weak[1000002];
str small[1000002];
bool cmp(str a, str b)
{
    if(a.qt == b.qt)
        return a.b < b.b;
    return a.qt < b.qt;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    int j = 0;
    sort(X, X+A);
    sort(Y, Y+B);
    for(int i = 0; i < T; ++i)
    {
        weak[i] = {W[i], S[i], i};
        small[i] = {S[i], W[i], i};
    }
    sort(weak, weak + T, cmp);
  //  for(int i = 0; i < T; ++i)
   //     cout << weak[i].qt << " " << weak[i].b << " " << weak[i].pi << '\n';
    sort(small, small + T, cmp);
    int b = 0;
    int e = 10000002;
    bool findd = 0;
    int ans = 0;
    while(b <= e)
    {
        int mid = (b + e) / 2;
        for(int i = 0; i < T; ++i)
            scos[i] = 0;
        deque<int>D;
        int ptra = 0;
        for(int i = 0; i < A; ++i)
        {
            while(ptra < T && X[i] > weak[ptra].qt)
                D.push_back(weak[ptra].pi), ++ptra;
            for(int j = 1; j <= mid && !D.empty(); ++j)
                scos[D.back()] = 1, D.pop_back();
        }
        ptra = T-1;
        D.clear();
        for(int i = B-1; i >= 0; --i)
        {
            while(ptra >= 0)
            {
                while(ptra >= 0 && scos[small[ptra].pi])
                    --ptra;
                if(ptra >= 0 && small[ptra].qt < Y[i])
                    D.push_front(small[ptra].pi), --ptra;
                else
                    break;
            }
            for(int j = 1; j <= mid && !D.empty(); ++j)
                scos[D.back()] = 1, D.pop_back();
        }
      //  cout << mid << " " << ptra << '\n';
        bool gg = 1;
        for(int i = 0; i < T; ++i)
            if(!scos[i])
                gg = 0;
        if(gg)
            findd = 1, ans = mid, e = mid - 1;
        else
            b = mid + 1;
    }
    if(!findd)
        return -1;
    return ans;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:29:9: warning: unused variable 'j' [-Wunused-variable]
     int j = 0;
         ^

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