Submission #587555

#	Time	Username	Problem	Language	Result	Execution time	Memory
587555		duyboy135	Distributing Candies (IOI21_candies)	C++17	29 / 100	123 ms	14416 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>

typedef std::pair<int, int> ii;

void push_to_stack(std::stack<long long> &st, long long toAdd){
    if(toAdd > 0){
        while(!st.empty() && st.top() + toAdd >= 0){
            toAdd += st.top();
            st.pop();
        }
        if(toAdd > 0)   st.push(toAdd);
    }
    else if(toAdd < 0){
        while(!st.empty() && st.top() + toAdd <= 0){
            toAdd += st.top();
            st.pop();
        }
        if(!st.empty() && toAdd < 0)    st.push(toAdd);
    }
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    int q = l.size();
    std::vector<int> s(n);
    std::vector<ii> orders;
    std::stack<long long> st;
    for(int i = 0; i < q; i++) push_to_stack(st, v[i]);
    for(int i = 0; i < n; i++)  orders.push_back(ii(c[i], i));
    sort(orders.begin(), orders.end());
    long long cur = 0;
    for(auto it = orders.begin(); it != orders.end(); it++){
        while(!st.empty() && it->first >= abs(st.top())){
            cur += st.top();
            st.pop();
        }
        if(st.size()%2) s[it->second] = (int) (cur + it->first);
        else s[it->second] = (int) cur;
    }
    return s;
}


//int main() {
//    freopen("test.inp","r",stdin);
//    int n;
//    assert(1 == scanf("%d", &n));
//    std::vector<int> c(n);
//    for(int i = 0; i < n; ++i) {
//        assert(scanf("%d", &c[i]) == 1);
//    }
//
//    int q;
//    assert(1 == scanf("%d", &q));
//    std::vector<int> l(q), r(q), v(q);
//    for(int i = 0; i < q; ++i) {
//        assert(scanf("%d %d %d", &l[i], &r[i], &v[i]) == 3);
//    }
//
//    std::vector<int> ans = distribute_candies(c, l, r, v);
//
//    for(int i = 0; i < n; ++i) {
//        if (i > 0) {
//            printf(" ");
//        }
//        printf("%d", ans[i]);
//    }
//    printf("\n");
//    fclose(stdout);
//    return 0;
//}

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