Submission #1247879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247879		clementine	Nile (IOI24_nile)	C++20	30 / 100	2097 ms	13372 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

// Base printer for general types
template<typename T>
void __print(const T& x) {
    cerr << x;
}

// Specialized printer for string
void __print(const string& x) { cerr << '"' << x << '"'; }
void __print(const char* x)   { cerr << '"' << x << '"'; }
void __print(char x)          { cerr << '\'' << x << '\''; }
void __print(bool x)          { cerr << (x ? "true" : "false"); }

// Specialized printer for pair
template<typename T1, typename T2>
void __print(const pair<T1, T2>& p) {
    cerr << "(";
    __print(p.first);
    cerr << ", ";
    __print(p.second);
    cerr << ")";
}

// For containers: vector, set, map, etc. (but not string or pair)
template<typename T, typename = void>
struct is_container : false_type {};

template<typename T>
struct is_container<T, std::void_t<decltype(begin(declval<T>())), decltype(end(declval<T>()))>> : true_type {};

template<typename T>
typename enable_if<is_container<T>::value && !is_same<T, string>::value, void>::type
__print(const T& container) {
    cerr << "{";
    bool first = true;
    for (const auto& item : container) {
        if (!first) cerr << ", ";
        __print(item);
        first = false;
    }
    cerr << "}";
}

// Recursive variadic template debug printer
template<typename T>
void _debug_cerr(const char* name, T&& value) {
    cerr << name << ": ";
    __print(value);
    cerr << '\n';
}

template<typename T, typename... Args>
void _debug_cerr(const char* names, T&& value, Args&&... args) {
    const char* comma = strchr(names, ',');
    cerr.write(names, comma - names) << ": ";
    __print(value);
    cerr << ", ";
    _debug_cerr(comma + 1, forward<Args>(args)...);
}

// Macro interface
#define debug(...) _debug_cerr(#__VA_ARGS__, __VA_ARGS__)


vector<pair<int ,int>> w; // first int is size, second is the index it is 
vector<int> diff;
vector<ll> pref;

// returns the maximum amount that can me saved in a range
ll find_min(int l, int r, int eval)
{
    debug(l, r, eval);
    ll region_tot = (l == 0) ? pref[r] : pref[r] - pref[l - 1];
    if((r - l + 1 ) % 2 == 0)
    {
        return region_tot;
    }
    // odd amount of things can't take all
    ll ans = 0;
    for(int i = l; i <= r; i ++)
    {
        if((i - l) % 2 == 0)// if your position is - l is even
        {
            // then you can take everything minus your current place
            ans = max(ans, region_tot - diff[i]);
        }
        else
        {
            if(abs(w[i-1].first - w[i+1].first) <=eval)
            {
                ans = max(ans, region_tot - diff[i]);
            }
        }
        // we consider pure odd case to be always worse than even case 
    }
    return ans;
}

vector<ll> calculate_costs(vector<int> W, vector<int> A,vector<int> B, vector<int> E) 
{
    int Q = (int)E.size();
    vector<ll> R(Q, 0);
    ll total_cost = 0;
    int n = (int) W.size();
    diff = vector<int>(n, 0);
    pref = vector<ll>(n, 0);
    vector<pair<int, int>> e; // first is D[i], second is index
    vector<int> segment_end(n, 0);
    for(int i = 0; i < n; i ++)
    {
        total_cost += A[i];
        w.push_back({W[i], i});
        segment_end[i] = i;
    }
    sort(w.begin(), w.end());
    for(int i = 0 ; i< Q; i ++)
    {
        e.push_back({E[i], i});
    }
    sort(e.begin(), e.end());

    for(int i = 0; i < n; i ++)
    {
        diff[i] = A[w[i].second] - B[w[i].second];
        (i !=0) ? pref[i] = pref[i-1] + diff[i] : pref[i] = diff[i];
    }
    for(auto eval: e)
    {
        debug(eval);
        ll ans = total_cost;
        debug(total_cost);
        int range_begin = 0;
        int range_end = 0;
        for(int i = 0; i < n-1; i ++)
        {
            if(abs(w[i].first - w[i+1].first) <= eval.first)
            {
                range_end = i + 1;
            }
            else
            {   
                ll temp = find_min(range_begin, range_end, eval.first);
                ans -= temp;
                debug(temp);
                range_begin = range_end = i + 1;
            }
        } 
        ll temp = find_min(range_begin, range_end, eval.first); 
        debug(temp);
        ans -= temp; // the off by one end needs to also be done   
        R[eval.second] = ans;
    }
    return R;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 0 / 17
• Subtask 4: 11 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18