Submission #83900

#	Time	Username	Problem	Language	Result	Execution time	Memory
83900		nikolapesic2802	Robots (IOI13_robots)	C++14	14 / 100	1106 ms	32144 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
#define pb push_back
using namespace std;
pair<int,int> maxx=make_pair(INT_MAX,INT_MAX);
int putaway(int a, int b, int t, int x[], int y[], int W[], int S[]) {
    sort(x,x+a);
    sort(y,y+b);
    reverse(y,y+b);
    vector<pair<int,int> > items(t);
    for(int i=0;i<t;i++)
    {
        items[i].first=W[i];
        items[i].second=S[i];
    }
    if(b==0)
    {
        //printf("usao!\n");
        multiset<int> s;
        while(items.size())
        {
            s.insert((items.back()).first);
            items.pop_back();
        }
        multiset<int>::iterator it=s.end();
        it--;
        if(*it>x[a-1])
            return -1;
        for(int res=1;res<=t;res++)
        {
            for(int i=0;i<a;i++)
            {
                it=s.lower_bound(x[i]);
                if(it==s.begin())
                    continue;
                it--;
                s.erase(it);
                if(s.size()==0)
                {
                    return res;
                }
            }
        }
    }
    items.pb(maxx);
    sort(items.begin(),items.end());
    vector<pair<int,int> > dodaj[a];
    int j=0;
    int cnt=0;
    for(int i=0;i<a;i++)
    {
        //printf("Usao za %i\n",x[i]);
        while(items[j].first<x[i])
        {
            //printf("Dodajem %i %i\n",items[j].first,items[j].second);
            dodaj[i].pb({items[j].second,cnt++});
            j++;
        }
    }
    int l=1,r=t+5;
    while(l<r)
    {
        int mid=(l+r)/2;
        //printf("%i\n",mid);
        j=0;
        int test=true;
        cnt=0;
        priority_queue<pair<int,int> > s;
        for(int i=0;i<a;i++)
        {
            int si=dodaj[i].size();
            for(int k=0;k<si;k++)
            {
                s.push(dodaj[i][k]);
                if(k>=si-mid)
                {
                    s.pop();
                }
            }
            for(int k=0;k<mid-si;k++)
            {
                if(s.empty())
                    break;
                s.pop();
                //printf("brisem!\n");
            }
        }
        for(;j<t;j++)
            s.push({items[j].second,cnt++});
        for(int i=0;i<b;i++)
        {
            //printf("usao! %i\n",y[i]);
            for(int k=0;k<mid;k++)
            {
                if(s.size()==0)
                {
                    break;
                    break;
                }
                if((s.top().first)<y[i])
                    s.pop();
                else
                {
                    break;
                    break;
                }
            }
        }
        if(s.size()!=0)
            test=false;
        if(test)
        {
            r=mid;
        }
        else
        {
            l=mid+1;
        }
    }
    if(l==t+5)
        return -1;
    return l;
}

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