Submission #962715

#	Time	Username	Problem	Language	Result	Execution time	Memory
962715		danikoynov	Robots (IOI13_robots)	C++14	100 / 100	313 ms	64684 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];

struct node
{
    int pos, mx;

    node (int _pos = -1, int _mx = -1)
    {
        pos = _pos;
        mx = _mx;
    }
};

node merge_node(node lf, node rf)
{
    if (lf.mx > rf.mx)
        return lf;
    return rf;
}

node tree[4 * maxt];
void build(int root, int left, int right)
{
    if (left == right)
    {
        tree[root].mx = toys[left].s;
        tree[root].pos = left;
        return;
    }

    int mid = (left + right) / 2;
    build(root * 2, left, mid);
    build(root * 2 + 1, mid + 1, right);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

void update(int root, int left, int right, int pivot)
{
    if (left == right)
    {
        tree[root].mx = -1;
        tree[root].pos = left;
        return;
    }

    int mid = (left + right) / 2;
    if (pivot <= mid)
        update(root * 2, left, mid, pivot);
    else
        update(root * 2 + 1, mid + 1, right, pivot);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

node query(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
        return node();

    if (left >= qleft && right <= qright)
        return tree[root];

    int mid = (left + right) / 2;
    return merge_node(query(root * 2, left, mid, qleft, qright),
                      query(root * 2 + 1, mid + 1, right, qleft, qright));
}


int to_x[maxn], stock[maxn];

int par[maxn];

int find_leader(int v)
{
    if (v == par[v])
        return v;
    return (par[v] = find_leader(par[v]));
}

int to_y[maxn];
bool check(int p)
{

    for (int i = 0; i <= a; i ++)
        par[i] = i, stock[i] = p;
    vector < toy > vec;
    for (int i = t - 1; i >= 0; i --)
    {
        int tk = find_leader(to_x[i]);
        int ds = to_x[i];
        while(ds < a && stock[ds] == 0)
          ds ++;

        if (tk == a)
        {
            vec.push_back(toys[i]);
        }
        else
        {

            stock[tk] --;
            if (stock[tk] == 0)
                par[tk] = tk + 1;
        }
    }


    reverse(vec.begin(), vec.end());

    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;



    sort(toys, toys + T, cmp_s);
    for (int i = 0; i < t; i ++)
    {
        int lf = 0, rf = a - 1;
        while(lf <= rf)
        {
            int mf = (lf + rf) / 2;
            if (x[mf] > toys[i].w)
                rf = mf - 1;
            else
                lf = mf + 1;
        }
        to_x[i] = lf;
    }
    int lf = 1, 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: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10