Submission #1015362

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015362		amine_aroua	Boxes with souvenirs (IOI15_boxes)	C++17	20 / 100	1 ms	604 KiB

boxes

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

#define intt long long
multiset<int> pos;
int l;
intt minDist(int i , int j)
{
    return min(abs(i - j) , l - abs(i - j));
}
int comb(int it1 , int it2 , int p)
{
    if(minDist(p , it1) > minDist(p , it2))
        return it2;
    return it1;
}
long long delivery(int N, int K, int L, int p[])
{
    l = L;
    for(int i = 0 ; i < N ; i++)
        pos.insert(p[i]);
    int beg = 0;
    intt ans = 0;
    while(!pos.empty())
    {
        int cnt = K;
        ans+= minDist(beg , 0);
        beg = 0;
        while(!pos.empty() && cnt--)
        {
            int best = *pos.begin();
            best = comb(best , *pos.rbegin() , beg);
            if(pos.lower_bound(beg) != pos.end())
            {
                best = comb(best , *pos.lower_bound(beg) , beg);
            }
            if(pos.lower_bound(beg) != pos.begin())
            {
                best = comb(best , *prev(pos.lower_bound(beg)) , beg);
            }
            ans+= minDist(best , beg);
            pos.erase(pos.find(best));
            beg = best;
        }
    }

    ans+= minDist(0 , beg);
    return ans;
}

/*
int main() {
    int N , K , L;
    cin>>N>>K>>L;
    vector<int> p(N);
    for(auto &x : p)
        cin>>x;
    cout<<delivery(N , K , L, p)<<endl;
}
*/

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