Submission #278796

#	Time	Username	Problem	Language	Result	Execution time	Memory
278796		ScarletS	Robots (IOI13_robots)	C++17	100 / 100	2346 ms	26016 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

bool ok(int k, vector<pair<int,int>> v, int X[], int Y[], int A, int B, int T)
{
    //cout<<"k = "<<k<<"\n";
    int cur=0;
    priority_queue<pair<int,int>> q;
    for (int i=0;i<A;++i)
    {
        //cout<<"currently on "<<X[i]<<"\n";
        while (cur<T)
        {
            if (v[cur].first>=X[i])
                break;
            q.push({v[cur].second,v[cur].first});
            ++cur;
        }
        for (int j=0;j<k&&sz(q);++j)
        {
            //cout<<q.top().first<<" "<<q.top().second<<"\n";
            q.pop();
        }
    }
    //cout<<sz(q)<<"!\n";
    while (cur<T)
    {
        q.push({v[cur].second,v[cur].first});
        ++cur;
    }
    //cout<<sz(q)<<"!\n";
    for (int i=0;i<B;++i)
    {
        for (int j=0;j<k&&sz(q);++j)
        {
            if (q.top().first>=Y[i])
            {
                //cout<<"oopsie\n";
                //cout<<q.top().first<<" "<<Y[i]<<"\n";
                return 0;
            }
            q.pop();
        }
    }
    if (sz(q))
        return 0;
    return 1;
}

int putaway(int A,int B,int T,
int X[],int Y[],int W[],int S[])
{
    int l=1,r=T,m;
    vector<pair<int,int>> v;
    for (int i=0;i<T;++i)
        v.push_back({W[i],S[i]});
    sort(v.begin(), v.end());
    sort(X,X+A);
    sort(Y,Y+B,greater<int>());
    if (!ok(T,v,X,Y,A,B,T))
        return -1;
    while (l<r)
    {
        m=l+(r-l)/2;
        if (ok(m,v,X,Y,A,B,T))
            r=m;
        else
            l=m+1;
    }
    return l;
}

/**int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int A,B,T;
    cin>>A>>B>>T;
    int X[A],Y[B],W[T],S[T];
    for (int i=0;i<A;++i)
        cin>>X[i];
    for (int i=0;i<B;++i)
        cin>>Y[i];
    for (int i=0;i<T;++i)
        cin>>W[i]>>S[i];
    cout<<putaway(A,B,T,X,Y,W,S);
    return 0;
}**/

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