Submission #554548

#	Time	Username	Problem	Language	Result	Execution time	Memory
554548		status_coding	Robots (IOI13_robots)	C++14	100 / 100	1524 ms	18272 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("unroll-loops")

using namespace std;

int n,a,b;

pair<int, int> val[1000005];

int weak[50005];
int small[50005];

bool ok(int nr)
{
    /*
    cout<<"debug\n";

    for(int i=1;i<=a;i++)
        cout<<weak[i]<<' ';
    cout<<"\n\n";

    for(int i=1;i<=b;i++)
        cout<<small[i]<<' ';
    cout<<"\n\n";

    for(int i=1;i<=n;i++)
        cout<<val[i].first<<' '<<val[i].second<<'\n';
    cout<<'\n';
    */

    int j=1;
    priority_queue<int> s;

    for(int i=1; i<=a; i++)
    {
        while(j<=n && val[j].first < weak[i])
        {
            s.push(val[j].second);
            j++;
        }

        int cnt = nr;
        while(!s.empty() && cnt)
        {
            cnt--;
            s.pop();
        }

    }

    while(j <= n)
    {
        s.push(val[j].second);
        j++;
    }

    /*
    cout<<"s ramas\n";
    for(int it : s)
        cout<<it<<' ';
    cout<<'\n';
    */

    for(int i=b; i>=1; i--)
    {
        int cnt = nr;

        while(!s.empty() && cnt)
        {
            cnt--;

            if(s.top() >= small[i])
                return false;

            s.pop();
        }
    }

    if(s.empty())
        return true;
    else
        return false;
}

int putaway(int A, int B, int N, int X[], int Y[], int W[], int S[])
{
    a = A;
    b = B;
    n = N;

    for(int i=1;i<=n;i++)
        val[i] = {W[i-1], S[i-1]};
    sort(val+1, val+n+1);


    for(int i=1;i<=a;i++)
        weak[i] = X[i-1];
    sort(weak+1, weak+a+1);

    for(int i=1;i<=b;i++)
        small[i] = Y[i-1];
    sort(small+1, small+b+1);

    for(int i=1;i<=n;i++)
        if(val[i].first >= weak[a] && val[i].second >= small[b])
            return -1;

    //cout<<ok(2)<<'\n';
    //return 0;

    int st=1, dr=n, mij, last=1;
    while(st <= dr)
    {
        mij = (st+dr)/2;

        if(ok(mij))
        {
            last = mij;
            dr = mij-1;
        }
        else
            st = mij+1;
    }

    return last;
}

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