Submission #623097

#	Time	Username	Problem	Language	Result	Execution time	Memory
623097		Hanksburger	Distributing Candies (IOI21_candies)	C++17	0 / 100	95 ms	8748 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> w, w2, w3, w4, ans;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    int n=c.size(), q=v.size(), mn, mx, cur;
    for (int i=1; i<q; i++)
        v[i]+=v[i-1];
    mn=mx=v[q-1];
    w.push_back(v[q-1]);
    for (int i=q-2; i>=0; i--)
    {
        if (mn>v[i])
        {
            mn=v[i];
            w.push_back(v[i]);
        }
        else if (mx<v[i])
        {
            mx=v[i];
            w.push_back(v[i]);
        }
    }
    if (w[w.size()-1]!=v[0])
        w.push_back(v[0]);
    reverse(w.begin(), w.end());
    w2.push_back(w[0]);
    for (int i=1; i<w.size(); i++)
        w2.push_back(w[i]-w[i-1]);
//    cout << "w:\n";
//    for (int i=0; i<w.size(); i++)
//    {
//        cout << w[i] << ' ' << w2[i] << '\n';
//    }
    cur=w2[0];
    for (int i=1; i<w2.size(); i++)
    {
        if ((w2[i-1]>0)^(w2[i]>0))
        {
            w3.push_back(cur);
            cur=w2[i];
        }
        else
            cur+=w2[i];
    }
    w3.push_back(cur);
    w4.push_back(w3[0]);
    for (int i=1; i<w3.size(); i++)
        w4.push_back(w4[i-1]+w3[i]);
//    cout << "w3:\n";
//    for (int i=0; i<w3.size(); i++)
//    {
//        cout << w3[i] << ' ' << w4[i] << '\n';
//    }
    if (w3.size()==1)
    {
        for (int i=0; i<n; i++)
        {
            int x=max(0, min(c[i], w3[0]));
            ans.push_back(x);
            continue;
        }
        return ans;
    }
    for (int i=0; i<n; i++)
    {
        if (abs(w3[1])<c[i])
        {
            int x=max(0, min(c[i], w3[0]));
            x=max(0, min(c[i], x+w3[1]));
            x+=w4[w4.size()-1]-w4[1];
            ans.push_back(x);
            continue;
        }
        int l=1, r=w3.size()-1;
        while (l<r)
        {
            int mid=(l+r+1)/2;
            if (abs(w3[mid])>=c[i])
                l=mid;
            else
                r=mid-1;
        }
        if (w3[l]>0)
        {
            int x=c[i]+w4[w4.size()-1]-w4[l];
            ans.push_back(x);
        }
        else
        {
            int x=w4[w4.size()-1]-w4[l];
            ans.push_back(x);
        }
    }
    return ans;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=1; i<w.size(); i++)
      |                   ~^~~~~~~~~
candies.cpp:37:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for (int i=1; i<w2.size(); i++)
      |                   ~^~~~~~~~~~
candies.cpp:49:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i=1; i<w3.size(); i++)
      |                   ~^~~~~~~~~~

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