Submission #1248894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248894		adrilen	Distributing Candies (IOI21_candies)	C++17	0 / 100	71 ms	11956 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int>l, std::vector<int> r, std::vector<int> v) {
    
    vector<ll> prefix;
    prefix.push_back(0);
    int n = v.size();
    for (int i = 0; i < n; i++) prefix.push_back(v[i] + prefix.back());
    vector<ll>min_prefix(n+1), max_prefix(n+1);
    min_prefix[n] = max_prefix[n] = prefix.back();
    for (int i = n - 1; i >= 0; i--)
    {
        min_prefix[i] = min(min_prefix[i+1], prefix[i]);
        max_prefix[i] = max(max_prefix[i + 1], prefix[i]);
    }

    // for (int i : prefix) cout << i << " ";
    // cout << "\n";
    // for (int i : min_prefix) cout << i << " ";
    // cout << "\n";
    // for (int i : max_prefix) cout << i << " ";
    // cout << "\n";

    n = c.size();
    vector<int> output(n);
    for (int i = 0; i < n; i++)
    {
        int lower = -1, upper = v.size(), mid;
        while (lower < upper)
        {
            mid = (lower + upper + 1) / 2;

            if (max_prefix[mid] - min_prefix[mid] >= c[i]) lower = mid;
            else upper = mid - 1;
        }

        if (lower == -1) {
            output[i] = prefix.back();
            continue;
        }

        if (max_prefix[lower] == max_prefix[lower + 1])
        {
            output[i] = c[i] - (max_prefix[lower] - prefix.back());
        } else {
            output[i] = prefix.back() -  min_prefix[lower];
        }
    }

    return output;
}


/*

1 4 -3 6 7 -5
1 5 2 8 15 10
1 2 2 8 10 10
15 15 15 15 15 10


c = 8 -> 3
*/

• Subtask 1: 0 / 3
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33