Submission #962677

#	Time	Username	Problem	Language	Result	Execution time	Memory
962677		danikoynov	Robots (IOI13_robots)	C++14	76 / 100	3086 ms	29084 KiB

robots

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

const int maxt = 1e6 + 10;
const int maxn = 1e5 + 10;

struct toy
{
    int w, s, idx;

    toy(int _w = 0, int _s = 0, int _idx = 0)
    {
        w = _w;
        s = _s;
    }
} toys[maxt];

bool cmp_w(toy t1, toy  t2)
{
    return t1.w < t2.w;
}

bool cmp_s(toy t1, toy t2)
{
    return t1.s < t2.s;
}

int x[maxn], y[maxn], used[maxt];
int a, b, t;


int cnt[maxn];
bool check(int p)
{
    for (int i = 0; i < t; i ++)
        used[i] = 0;
    for (int i = 0; i < a; i ++)
    {
         //cout << i << endl;
        int lf = 0, rf = t - 1;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (toys[mf].w < x[i])
                lf = mf + 1;
            else
                rf = mf - 1;
        }

        //cout << "Survived" << endl;
        vector < toy > vec;
        for (int j = 0; j < lf; j ++)
            if (!used[j])
                vec.push_back(toys[j]);

        sort(vec.begin(), vec.end(), cmp_s);

        int step = 0;
        while(!vec.empty() && step < p)
        {
            used[vec.back().idx] = 1;
            vec.pop_back();
            step ++;
        }
    }


    vector < toy > vec;
    for (int i = 0; i < t; i ++)
        if (!used[i])
            vec.push_back(toys[i]);

    sort(vec.begin(), vec.end(), cmp_s);
    for (int i = 0; i < b; i ++)
        cnt[i] = 0;
    int pivot = 0;
    for (toy cur : vec)
    {
        while(pivot < b && (cur.s >= y[pivot] || cnt[pivot] == p))
            pivot ++;
        if (pivot == b)
            return false;
        cnt[pivot] ++;
    }

    return true;
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])
{
    a = A;
    b = B;
    t = T;

    for (int i = 0; i < T; i ++)
    {
        toys[i] = toy(W[i], S[i]);
    }

    for (int i = 0; i < a; i ++)
        x[i] = X[i];
    for (int i = 0; i < b; i ++)
        y[i] = Y[i];


    sort(x, x + A);
    sort(y, y + B);
    sort(toys, toys + T, cmp_w);


    for (int i = 0; i < T; i ++)
        toys[i].idx = i;
    int lf = 0, rf = T;
    while(lf <= rf)
    {

        int mf = (lf + rf) / 2;
        if (check(mf))
            rf = mf - 1;
        else
            lf = mf + 1;
    }

    if (lf > T)
        return - 1;
    return lf;
}

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