Submission #220334

#	Time	Username	Problem	Language	Result	Execution time	Memory
220334		XmtosX	Robots (IOI13_robots)	C++17	76 / 100	3098 ms	32120 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