Submission #220342

#	Time	Username	Problem	Language	Result	Execution time	Memory
220342		XmtosX	Robots (IOI13_robots)	C++17	76 / 100	953 ms	65540 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[11];
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,last=0,lol=0;
    s1.insert(make_pair(2e9+1,0));
    while (low<=high)
    {
        if (!s[lol].empty())
            s[lol].clear();
        for (int i=0;i<B;i++)
        {
            if (cur[i]==last)
                s1.insert(make_pair(Y[i],i));
            cur[i]=0;
        }
        mid= (low+high)/2;
        last=mid;
        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[lol].insert(p[i].second);
            if (!x)
            {
                if (s[lol].empty())
                {
                    yes=false;
                    break;
                }
                it= s1.lower_bound(make_pair(*s[lol].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[lol].erase(s[lol].begin());
            }
            else
            {
                x--;
            }
        }
        lol++;
        lol%=10;
        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