Submission #767372

#	Time	Username	Problem	Language	Result	Execution time	Memory
767372		caganyanmaz	Boxes with souvenirs (IOI15_boxes)	C++17	0 / 100	2066 ms	340 KiB

boxes

    #include <bits/stdc++.h>
    #ifdef DEBUGGING
    #define debug(x) cout << (#x) << ": " << (x) << "\n";
    #else
    #define debug(x)
    #endif
    #include "boxes.h"
    #define int long long
    using namespace std;
     
    void find_insert(int pos, set<array<int, 2>>& s)
    {
            auto it = s.lower_bound(array<int,2>({pos, -1}));
            int val = 0;
            if ((*it)[0] == pos)
            {
                    val = (*it)[1];
                    s.erase(it);
            }
            s.insert({pos, val+1});
    }
     
    int get_sum(set<array<int, 2>>& s)
    {
            int sum = 0;
            for (auto [pos, val] : s)
                    sum += val;
            return sum;
    }
     
    int calculate_left(set<array<int, 2>>& left, int K)
    {
            debug("AA");
            int cost = 0;
            int pr = 0;
            for (auto it = left.rbegin(); it != left.rend(); it++)
            {
                    auto [pos, val] = *it;
                    if (val > pr)
                    {
                            val -= pr;
                            pr = 0;
                            int steps = val / K;
                            if ((val % K) != 0)
                            {
                                    pr = K - (val % K);
                                    steps++;
                            }
                            cost += steps * (pos * 2);
                    }
                    else
                    {
                            pr -= val;
                    }
            }
            debug("AB");
            return cost;
    }
     
    int calculate_right(set<array<int,2>>& right, int K, int L)
    {
            debug("BA");
            int cost = 0;
            int pr = 0;
            for (auto [pos, val] : right)
            {
                    if (val > pr)
                    {
                            val -= pr;
                            pr = 0;
                            int steps = val / K;
                            if ((val % K) != 0)
                            {
                                    steps++;
                                    pr = K - (val % K);
                            }
                            cost += steps * (L - pos) * 2;
     
                    }
            }
            debug("BB");
            return cost;
    }
     
     
    int calculate_steps(int a, int K)
    {
            int steps = a / K;
            if ((a % K) != 0)
                    steps++;
            return steps;
    }
     
    int delivery(int32_t N, int32_t K, int32_t L, int32_t p[])
    {
            debug("A");
            set<array<int, 2>> left, right;
            int mid = 0;
            for (int i = 0; i < N; i++)
            {
                    if (p[i] > L / 2)
                            find_insert(p[i], right);
                    else if (p[i] < L / 2)
                            find_insert(p[i], left);
                    else
                            mid++;
            }
            debug("B");
            int left_sum = get_sum(left), right_sum = get_sum(right);
            debug("E");
            int left_leftover = left_sum % K, right_leftover = right_sum % K;
            int llc = calculate_left(left, K), rlc = calculate_right(right, K, L);
            int tmp = left_leftover;
            debug("C");
            for (auto it = left.rbegin(); it != left.rend() && tmp > 0;)
            {
                    int dec = min((*it)[1], tmp);
                    tmp -= dec;
                    array<int, 2> new_value = *it;
                    new_value[1] -= dec;
                    it = decltype(it)(left.erase(next(it).base()));
                    if (new_value[1] > 0)
                    {
                            left.insert(new_value);
                            break;
                    }
            }
            debug("C");
            tmp = right_leftover;
            for (auto it = right.begin(); it != right.end() && tmp > 0;)
            {
                    int dec = min((*it)[1], tmp);
                    tmp -= dec;
                    array<int, 2> new_value = *it;
                    new_value[1] -= dec;
                    it = right.erase(it);
                    if (new_value[1] > 0)
                    {
                            right.insert(new_value);
                            break;
                    }
            }
            debug("D");
            int lwlc = calculate_left(left, K), rwlc = calculate_right(right, K, L);
            int best = min({
                            llc + rlc + L * calculate_steps(mid, K),
                            lwlc + rlc + L * calculate_steps(mid + left_leftover, K),
                            llc + rwlc + L * calculate_steps(mid + right_leftover, K),
                            lwlc + rwlc + L * calculate_steps(mid + left_leftover + right_leftover, K)
                            });
            return best;
    }

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30