Submission #92892

#	Time	Username	Problem	Language	Result	Execution time	Memory
92892		stefdasca	Robots (IOI13_robots)	C++14	53 / 100	412 ms	23740 KiB

robots

#include"robots.h"
#include<bits/stdc++.h>
using namespace std;
bool scos[1000002];
int pos[1000002];
struct str
{
    int quantity;
    bool tip;
    int pi;
};
str v[2000002];
bool cmp(str a, str b)
{
    if(a.quantity == b.quantity)
        return pos[a.pi] > pos[b.pi];
    return a.quantity < b.quantity;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    int j = 0;
    sort(X, X+A);
    sort(Y, Y+B);
    for(int i = 0; i < T; ++i)
    {
        if(W[i] < X[A-1])
            ++pos[i];
        if(S[i] < Y[B-1])
            ++pos[i];
        if(A)
            v[j++] = {W[i], 0, i};
        if(B)
            v[j++] = {S[i], 1, i};

    }
    sort(v, v + j, cmp);
    int b = 0;
    int e = 10000002;
    bool findd = 0;
    int ans = 0;
    while(b <= e)
    {
        int mid = (b + e) / 2;
        for(int i = 0; i < T; ++i)
            scos[i] = 0;
        int Pa = A-1;
        int Pb = B-1;
        int Ta = (A > 0) * mid;
        int Tb = (B > 0) * mid;
        for(int i = j-1; i >= 0; --i)
        {
            if(scos[v[i].pi])
                continue;
            if(v[i].tip == 0 && (Pa + Ta == 0))
                continue;
            if(v[i].tip == 1 && (Pb + Tb == 0))
                continue;
            if(v[i].tip == 0 && v[i].quantity < X[Pa])
            {
                scos[v[i].pi] = 1;
                --Ta;
                if(Ta == 0 && Pa)
                    --Pa, Ta = mid;
            }
            if(v[i].tip == 1 && v[i].quantity < Y[Pb])
            {
                scos[v[i].pi] = 1;
                --Tb;
                if(Tb == 0 && Pb)
                    --Pb, Tb = mid;
            }
        }
        bool gg = 1;
        for(int i = 0; i < T; ++i)
            if(!scos[i])
                gg = 0;
        if(gg)
            findd = 1, ans = mid, e = mid - 1;
        else
            b = mid + 1;
    }
    if(!findd)
        return -1;
    return ans;
}

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