Submission #1257255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257255		wheelert	Hacker (BOI15_hac)	C++20	20 / 100	80 ms	4168 KiB

hac

#include <iostream>                                                                        
#include <vector>                                                                          
#include <deque>                                                                           
                                                                                           
                                                                                           
using namespace std;                                                                       
                                                                                           
                                                                                           
int naive_solution(vector<int> const& arr) {                                               
    int N = arr.size();                                                                    
    int num_window = ( N + 1 ) / 2;                                                        
    // for each spot                                                                       
    //      there are (num_window) subranges of length (num_window) containing node[i]     
    //          villain can force us to choose have any of these, so playing               
    //          optimally he will choose the one that minimizes our score                  
    //                                                                                     
                                                                                           
    static constexpr int INF = 1'000'000'000;                                              
    vector<int> min_answer_per_node(N, INF);                                               
    // naive solution                                                                      
    for (int i = 0; i < N; ++i) {                                                          
                                                                                           
        for (int j = 0; j < num_window; ++j) {                                             
                                                                                           
            int subrange_sum = 0;                                                          
            int subrange_start = i + j - num_window + 1;                                   
            for (int k = 0; k < num_window; ++k) {                                         
                subrange_sum += arr[(subrange_start + k + N) % N];                         
            }                                                                              
                                                                                           
            min_answer_per_node[i] = std::min(min_answer_per_node[i], subrange_sum);       
        }                                                                                  
    }                                                                                      
                                                                                           
    int answer = min_answer_per_node[0];                                                   
    for (int i = 1; i < N; ++i)                                                            
        answer = std::max(min_answer_per_node[i], answer);                                 
    return answer;                                                                         
}                                                                                          
                                                                                           
                                                                                           
int optimal_solution(vector<int> const& arr)                                               
{                                                                                          
    int N = arr.size();                                                                    
    int num_window = ( N + 1 ) / 2;                                                        
    // invariant - (index, val) in window min is always sorted in increasing order         
    //           - querying the min can always be done by accessing front()                
    //                                                                                     
    deque<pair<int, int>> window_min{};                                                    
                                                                                           
    auto insert = [&](int index, int val) {                                                
        while (window_min.size() > 0 && window_min.back().second > val)                    
            window_min.pop_back();                                                         
                                                                                           
        window_min.emplace_back( index, val );                                             
    };                                                                                     
                                                                                           
    auto pop_to = [&](int index) {                                                         
        while (window_min.size() > 0 && window_min.front().first <= index)                 
            window_min.pop_front();                                                        
    };                                                                                     
                                                                                           
    static constexpr int INF = 1'000'000'000;                                              
    vector<int> min_answer_per_node(N, INF);                                               
    int subrange_sum = 0;                                                                  
    for (int k = 0; k < num_window; ++k) {                                                 
              subrange_sum += arr[(0 - num_window + 1 + k + N) % N];                                     
    }                                                                                              
    for (int j = 0; j < num_window; ++j) {                                                         
        insert(j, subrange_sum);                                                                   
                                                                                                   
        int subrange_start = (j - num_window + 1 + N) % N;                                         
        int subrange_end = j;                                                                      
        //std::cout << "start: " << subrange_start << " end: " << subrange_end << std::endl;       
        //std::cout << subrange_sum << endl;                                                       
        subrange_sum += arr[(j + 1 + N) % N];                                                      
        subrange_sum -= arr[(j - num_window + 1 + N) % N];                                         
    }                                                                                              
    for (int i = 0; i < N ; ++i) {                                                                 
        min_answer_per_node[i] = window_min.front().second;                                        
        pop_to(i);                                                                                 
                                                                                                   
        subrange_sum += arr[(i + num_window + N) % N];                                             
        subrange_sum -= arr[i];                                                                    
        insert(i + num_window, subrange_sum);                                                      
    }                                                                                              
                                                                                                   
    int answer = 0;                                                                                
    for (int i = 0; i < N; ++i) answer = std::max(min_answer_per_node[i], answer);                 
    return answer;                                                                                 
}                                                                                                  
                                                                                                   
// test driver                                                                                     
int main()                                                                                         
{                                                                                                  
    int N;                                                                                         
    cin >> N;                                                                                      
                                                                                                   
    vector<int> arr(N);                                                                            
    for (int i = 0; i < N; ++i) cin >> arr[i];                                                     
                                                                                                   
    // std::cout << "naive: " << naive_solution(arr) << std::endl;                                 
    // std::cout << "optimal: " << optimal_solution(arr) << std::endl;                             
    std::cout << optimal_solution(arr) << std::endl;                                               
}                                                                                                  

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 40