Submission #554542

#	Time	Username	Problem	Language	Result	Execution time	Memory
554542		status_coding	Robots (IOI13_robots)	C++14	76 / 100	3068 ms	28988 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;

int n,a,b;

pair<int, int> val[1000005];

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

bool comp(int x, int y)
{
    return val[x].first < val[y].first;
}

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;
    multiset<int> s;

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

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

            auto it = s.end();
            it--;

            s.erase(it);
        }
    }

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

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

    for(int i=1; i<=b; i++)
    {
        int cnt = nr;

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

            auto it = s.lower_bound(small[i]);

            if(it == s.begin())
                break;

            it--;
            s.erase(it);
        }
    }

    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: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10