Submission #1193193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193193		alexdd	Distributing Candies (IOI21_candies)	C++20	0 / 100	61 ms	8264 KiB

candies

#include "candies.h"

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

int n;
const int INF = 1e9;

vector<int> v;
int calc(int lim)
{
    int cur=0;
    for(int i=0;i<v.size();i++)
    {
        cur += v[i];
        cur = max(cur, 0);
        cur = min(cur, lim);
    }
    return cur;
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> copv)
{
    v = copv;
    n = c.size();

    int e0 = calc(0), eINF = calc(INF);
    int st=0,dr=INF,ans=0;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(calc(mij) == e0)
        {
            ans = mij;
            st = mij+1;
        }
        else
            dr = mij-1;
    }
    int mic = ans;

    st=0,dr=INF,ans=INF;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(calc(mij) == eINF)
        {
            ans = mij;
            dr = mij-1;
        }
        else
            st = mij+1;
    }
    int mare = ans;

    long long tot=0;
    for(int i=0;i<v.size();i++)
        tot += v[i];

    vector<int> sol(n);
    for(int i=0;i<n;i++)
    {
        if(c[i] <= mic)
            sol[i] = e0;
        else if(c[i] >= mare)
            sol[i] = eINF;
        else
        {
            assert(0 <= (long long)c[i] + tot && (long long)c[i] + tot <= c[i]);
            sol[i] = c[i] + tot;
        }
    }
    return sol;
}

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