Submission #1288099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288099		ortsac	Boxes with souvenirs (IOI15_boxes)	C++20	10 / 100	2 ms	584 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<long long, long long>
#define fr first
#define se second

int n, k, l;

int dist(int a, int b) {
    if (a > b) swap(a, b);
    if (a == 0) return min(b, l - b);
    return min(b - a, dist(0, a) + dist(0, b));
}

int delivery(int32_t N, int32_t K, int32_t L, int32_t p[]) {
    n = N, k = K, l = L;
    map<int, int> pos;
    for (int i = 0; i < n; i++) pos[p[i]]++;
    deque<pii> v = {{0, 0}};
    for (auto [a, b] : pos) v.push_back({a, b});
    v.push_back({0, 0});
    int cval, ans, lst;
    deque<pii> bv = v;
    n = v.size(); 
    // run one
    v = bv;
    cval = k, ans = 0;
    lst = 0;
    vector<int> pf(n), repf(n), pf2(n), arrPf(n);
    for (int i = 0; i < n; i++) {
        auto& [po, need] = v[i];
        ans += dist(lst, po);
        // get whatever is needed done in here
        pf2[i] = ans;
        arrPf[i] = cval;
        repf[i] = max(0LL, need - cval);
        while (need > cval) {
            need -= cval;
            ans += 2*dist(0, po);
            cval = k;
        }
        cval -= need;
        need = 0;
        pf[i] = ans;
        // go to next one
        lst = po;
    }
    // run 2
    v = bv;
    vector<int> sf(n), resf(n), sf2(n), arrSf(n);
    cval = k, ans = 0;
    lst = 0;
    for (int i = n - 1; i >= 0; i--) {
        auto& [po, need] = v[i];
        ans += dist(lst, po);
        // get whatever is needed done in here
        sf2[i] = ans;
        arrSf[i] = cval;
        resf[i] = max(0LL, need - cval);
        while (need > cval) {
            need -= cval;
            ans += 2*dist(0, po);
            cval = k;
        }
        cval -= need;
        need = 0;
        sf[i] = ans;
        // go to next one
        lst = po;
    }
    // calc ans for remaining stuff
    int mians = min(pf[n - 1], sf[0]);
    for (int i = 0; i < n; i++) {
        int po = v[i].fr;
        int qsf = 0, qpf = 0, nans = 0;
        // did pf first, now sf
        cval = arrSf[i]; // quando o sf tinha isso de cval
        nans = pf2[i] + sf2[i] + 2*dist(v[i].fr, 0);
        while (repf[i] > cval) {
            repf[i] -= cval;
            nans += 2*dist(0, po);
            cval = k;
        }
        mians = min(mians, nans);
        // did sf first, now pf
        cval = arrPf[i]; // quando o pf tinha isso de cval
        nans = pf2[i] + sf2[i] + 2*dist(v[i].fr, 0);
        while (resf[i] > cval) {
            resf[i] -= cval;
            nans += 2*dist(0, po);
            cval = k;
        }
        mians = min(mians, nans);
    }
    // calc ans
    for (int i = 0; i < n; i++) {
        if ((i + 1) < n) mians = min(mians, pf[i] + sf[i + 1] + dist(v[i].fr, 0) + dist(v[i + 1].fr, 0));
        if (i > 0) mians = min(mians, pf[i - 1] + sf[i] + dist(v[i].fr, 0) + dist(v[i - 1].fr, 0));
    }
    // print
    //cout << mians << "\n";
    return mians;
}

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