Submission #281744

#	Time	Username	Problem	Language	Result	Execution time	Memory
281744		Kastanda	Robots (IOI13_robots)	C++11	100 / 100	601 ms	26364 KiB

robots

// M
#include<bits/stdc++.h>
#include "robots.h"
using namespace std;
const int N = 50004, MXN = 1e6 + 3;
int n, m, k, X[N], Y[N], W[MXN], S[MXN], PS[N], C[N];
vector < int > V[N];
priority_queue < int > Pq;
inline bool Solve(int md)
{
        long long Cnt = 0; Pq = {};
        memset(C, 0, sizeof(C));
        memset(PS, 0, sizeof(PS));

        auto Push = [&](int val) {
                if (!C[val])
                        Pq.push(-val);
                C[val] ++;
        };
        auto Pop = [&]() {
                int val = -Pq.top();
                C[val] --;
                if (!C[val])
                        Pq.pop();
                return val;
        };

  int tp2 = 0;
        for (int i = n; i >= 0; i --)
        {
                for (int a : V[i])
                        Push(a);
                if (i < n)
                        Cnt += md;
                Cnt -= (int)V[i].size();
                while (Cnt < 0)
                {
                  PS[Pop()] ++, Cnt ++;
                  tp2 ++;
                  if (tp2 > 1LL * m * md)
                    return 0;
                }
        }
        Cnt = 0;
        for (int i = m; i >= 0; i --)
        {
                if (i < m)
                        Cnt += md;
                Cnt -= PS[i];
                if (Cnt < 0)
                        return 0;
        }
        return 1;
}
int putaway(int _n, int _m, int _k, int _X[], int _Y[], int _W[], int _S[])
{
        n = _n; m = _m; k = _k;
        for (int i = 0; i < n; i ++)
                X[i] = _X[i];
        for (int i = 0; i < m; i ++)
                Y[i] = _Y[i];
        for (int i = 0; i < k; i ++)
                W[i] = _W[i], S[i] = _S[i];
        sort(X, X + n);
        sort(Y, Y + m);
        for (int i = 0; i < k; i ++)
        {
                int jx = upper_bound(X, X + n, W[i]) - X;
                int jy = upper_bound(Y, Y + m, S[i]) - Y;
                V[jx].push_back(jy);
        }
        for (int i = 0; i <= n; i ++)
                sort(V[i].begin(), V[i].end());

        if (!Solve(k))
                return -1;

        int le = 0, ri = k, md;
        while (ri - le > 1)
        {
                md = (le + ri) >> 1;
                if (Solve(md))
                        ri = md;
                else
                        le = md;
        }
        return ri;
}

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