Submission #962689

#	Time	Username	Problem	Language	Result	Execution time	Memory
962689		danikoynov	Robots (IOI13_robots)	C++14	0 / 100	27 ms	51036 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];
bool check(int p)
{
    for (int i = 0; i < t; i ++)
        used[i] = 0;

     build(1, 0, t - 1);
    for (int i = 0; i < a; i ++)
    {
         //cout << i << endl;


        //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(step < p)
        {
             node cur = query(1, 0, t - 1, 0, to_x[i]);
             if (cur.mx == -1)
               break;
             used[cur.pos] = 1;
             update(1, 0, t - 1, cur.pos);
            //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 < a; i ++)
    {
                 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;
        }
        to_x[i] = rf;
    }
    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: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10