Submission #219546

#	Time	Username	Problem	Language	Result	Execution time	Memory
219546		XmtosX	Robots (IOI13_robots)	C++17	76 / 100	3087 ms	31992 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1e6;
pair<int,int> p[N];
multiset<pair<int,int> > s1;
multiset<pair<int,int> > ::iterator it;
multiset<int> s;
int cur[50004];
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    for (int i=0;i<T;i++)
    {
        p[i]={W[i],S[i]};
    }
    sort(p,p+T);
    sort(X,X+A);
    reverse(p,p+T);
    reverse(X,X+A);
    int low=1,high=T,ans=-1,mid;
    while (low<=high)
    {
        s.clear();
        s1.clear();
        memset(cur,0,sizeof cur);
        for (int i=0;i<B;i++)
        {
            s1.insert(make_pair(Y[i],i));
        }
        s1.insert(make_pair(2e9+1,0));
        mid= (low+high)/2;
        long long x=0;
        int cnt=0;
        bool yes=true;
        for (int i=0;i<T;i++)
        {
            while (cnt<A&&p[i].first<X[cnt])
            {
                cnt++;
                x+=mid;
            }
            s.insert(p[i].second);
            if (!x)
            {
                if (s.empty())
                {
                    yes=false;
                    break;
                }
                it= s1.lower_bound(make_pair(*s.begin(),B));
                if ((*it).first==2e9+1)
                {
                    yes=false;
                    break;
                }
                pair<int,int> P= *it;
                cur[P.second]++;
                if (cur[P.second]==mid)
                {
                    s1.erase(it);
                }
                s.erase(s.begin());
            }
            else
            {
                x--;
            }
        }
        if (yes)
        {
            ans=mid;
            high=mid-1;
        }
        else
            low=mid+1;
    }
    return ans;
}

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