Submission #944405

#	Time	Username	Problem	Language	Result	Execution time	Memory
944405		wii	Robots (IOI13_robots)	C++17	90 / 100	3037 ms	47784 KiB

robots

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

const int MaxN = 5e4 + 5;
int cnt[MaxN], jump[MaxN];
priority_queue<int, vector<int>, greater<int>> q[MaxN];

template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; }


struct comp {
    bool operator() (int x, int y) const {
        if (q[x].size() == q[y].size())
            return x < y;

        return q[x].size() > q[y].size();
    }
};

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    bool impossible = false;

    function<void(int)> pushSize = [&](int s) {
        int id = upper_bound(Y, Y + B, s) - Y;
        if (id < B)
            cnt[id] += 1;
        else impossible = true;
    };

    function<void(int, int)> pushWeight = [&](int w, int s) {
        int id = upper_bound(X, X + A, w) - X;

        if (id < A)
            q[id].push(s);
        else pushSize(s);
    };

    function<int(int, int)> movetoTop = [&](int u, int top) {
        if (u >= A)
            return u;

        if (q[u].size() > top)
            return jump[u] = movetoTop(jump[u], top);
        else
            return u;
    };

    function<void(int)> balance = [&](int lim) {
        for (int i = 0; i < B; ++i) {
            if (cnt[i] > lim)
                cnt[i + 1] += cnt[i] - lim, cnt[i] = lim;
        }

        if (cnt[B] > lim)
            impossible = true;
    };

    function<bool(int)> check = [&](int lim) {
        int remain = 0;
        for (int i = 0; i < B; ++i) {
            remain = (cnt[i] + remain > lim) ? cnt[i] + remain - lim : 0;
        }
        return remain == 0;
    };

    function<int()> auto_balanced = [&]() {
        int sum = 0;
        for (int i = 0; i < B; ++i)
            sum += cnt[i];

        int l = (sum / B) + (sum % B != 0), r = *max_element(cnt, cnt + B);
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid))
                r = mid - 1;
            else
                l = mid + 1;
        }
        return r + 1;
    };

    sort(X, X + A);
    sort(Y, Y + B);

    for (int i = 0; i < A; ++i)
        jump[i] = i + 1;

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

    if (impossible)
        return -1;

    // cout << "???" << endl;

    set<int, comp> s;
    for (int i = 0; i < A; ++i) if (!q[i].empty())
        s.insert(i);

    int lst = -1, res = max(auto_balanced(), s.empty() ? 0 : (int)q[*s.begin()].size());
    while (!s.empty()) {
        int u = *s.begin(); s.erase(s.begin());
        int v = movetoTop(u, q[u].size() - 1);

        if (lst != q[u].size()) {
            int r = auto_balanced();
            minimize(res, max(r, (int)q[u].size()));

            impossible |= r > q[u].size();
            if (impossible) {
                return res;
            }
        }

        if (q[u].empty())
            break;

        lst = q[u].size();

        int Size = q[u].top(); q[u].pop();

        if (v < A) {
            s.erase(v);
            q[v].push(Size);
            s.insert(v);
        } else {
            pushSize(Size);
            if (impossible) {
                minimize(res, max(auto_balanced(), lst));
                // cout << "??" << endl;
                return res;
            }
        }

        s.insert(u);
    }

    // return -1;
    return min(res, auto_balanced());
}

Compilation message (stderr)

robots.cpp: In lambda function:
robots.cpp:44:25: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |         if (q[u].size() > top)
      |             ~~~~~~~~~~~~^~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:108:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         if (lst != q[u].size()) {
      |             ~~~~^~~~~~~~~~~~~~
robots.cpp:112:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             impossible |= r > q[u].size();
      |                           ~~^~~~~~~~~~~~~

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