oj.uz

Submission #623249

# Submission time Handle Problem Language Result Execution time Memory
623249 2022-08-05T11:15:34 Z Hanksburger Distributing Candies (IOI21_candies) C++17
29 / 100
 108 ms 11456 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
vector<long long> w, w2, w3, w4;
vector<int> ans;
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v)
{
    long long n=c.size(), q=v.size(), mn, mx, cur;
    for (long long i=1; i<q; i++)
        v[i]+=v[i-1];
    mn=mx=v[q-1];
    w.push_back(v[q-1]);
    for (long long 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]);
        }
    }
    reverse(w.begin(), w.end());
    w2.push_back(w[0]);
    for (long long i=1; i<w.size(); i++)
        w2.push_back(w[i]-w[i-1]);
//    cout << "w:\n";
//    for (long long i=0; i<w.size(); i++)
//    {
//        cout << w[i] << ' ' << w2[i] << '\n';
//    }
    cur=w2[0];
    for (long long 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 (long long i=1; i<w3.size(); i++)
        w4.push_back(w4[i-1]+w3[i]);
//    cout << "w3:\n";
//    for (long long i=0; i<w3.size(); i++)
//    {
//        cout << w3[i] << ' ' << w4[i] << '\n';
//    }
    if (w3.size()==1)
    {
        for (long long i=0; i<n; i++)
        {
            long long x=max(0LL, min(c[i]+0LL, w3[0]));
            ans.push_back(x);
            continue;
        }
        return ans;
    }
    for (long long i=0; i<n; i++)
    {
        if (abs(w3[1])<c[i])
        {
            long long x=max(0LL, min(c[i]+0LL, w3[0]));
            x=max(0LL, min(c[i]+0LL, x+w3[1]));
            x+=w4[w4.size()-1]-w4[1];
            ans.push_back(x);
            continue;
        }
        long long l=1, r=w3.size()-1;
        while (l<r)
        {
            long long mid=(l+r+1)/2;
            if (abs(w3[mid])>=c[i])
                l=mid;
            else
                r=mid-1;
        }
        if (w3[l]>0)
        {
            long long x=c[i]+w4[w4.size()-1]-w4[l];
            ans.push_back(x);
        }
        else
        {
            long long 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:28:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (long long i=1; i<w.size(); i++)
      |                         ~^~~~~~~~~
candies.cpp:36:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (long long i=1; i<w2.size(); i++)
      |                         ~^~~~~~~~~~
candies.cpp:48:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (long long i=1; i<w3.size(); i++)
      |                         ~^~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 108 ms 9388 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
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 48 ms 4964 KB Output is correct
4 Correct 49 ms 3680 KB Output is correct
5 Correct 88 ms 8276 KB Output is correct
6 Correct 104 ms 8284 KB Output is correct
7 Correct 99 ms 8156 KB Output is correct
8 Correct 91 ms 8280 KB Output is correct
9 Correct 93 ms 11456 KB Output is correct

Subtask #5
0 / 33.0

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