oj.uz

Submission #623097

# Submission time Handle Problem Language Result Execution time Memory
623097 2022-08-05T07:35:11 Z Hanksburger Distributing Candies (IOI21_candies) C++17
0 / 100
 95 ms 8748 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 8748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -