Submission #856441

#	Time	Username	Problem	Language	Result	Execution time	Memory
856441		onepunchac168	Robots (IOI13_robots)	C++14	100 / 100	2616 ms	25412 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
typedef pair <int ,int > ii;
const int N=1e6+5;
const int M=5e4+5;
int x[M],y[M];
int ca[M],cb[M];

int n,m,s;
ii w[N];
bool check(int mid)
{
    for (int i=1;i<=n;i++)
    {
        ca[i]=mid;
    }
    multiset <ii> st;
    for (int i=1;i<=m;i++)
    {
        st.insert({y[i],mid});
    }
    int ida=n;
    for (int i=1;i<=s;i++)
    {
        auto pp=st.upper_bound({w[i].se,1e9+5});
        if (pp!=st.end())
        {
            if ((*pp).se==1)
            {
                st.erase(pp);
            }
            else
            {
                ii gg={(*pp).fi,(*pp).se-1};
                st.erase(pp);
                st.insert(gg);
            }
        }
        else
        {
            if (ca[ida]==0)
            {
                ida--;
            }
            if (ida==0||x[ida]<=w[i].fi)
            {
                return false;
            }
            ca[ida]--;
        }
    }
    return true;

}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    int ans=-1;
    int left=1;
    int right=T;
    n=A;
    m=B;
    s=T;
    for (int i=1;i<=A;i++)
    {
        x[i]=X[i-1];
    }
    sort (x+1,x+n+1);
    for (int i=1;i<=B;i++)
    {
        y[i]=Y[i-1];
    }
    sort (y+1,y+m+1);
    for (int i=1;i<=T;i++)
    {
        w[i].fi=W[i-1];
        w[i].se=S[i-1];
    }
    sort (w+1,w+s+1,greater <ii> ());
    while (left<=right)
    {
        int mid=(left+right)/2;
        if (check(mid)==true)
        {
            ans=mid;
            right=mid-1;
        }
        else left=mid+1;
    }
    return ans;
}

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