Submission #1257271

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257271		wheelert	Hacker (BOI15_hac)	C++20	20 / 100	1096 ms	420 KiB

hac

#include <iostream>                                                                                              
#include <vector>                                                                                                
#include <deque>                                                                                                 
                                                                                                                 
                                                                                                                 
using namespace std;                                                                                             
                                                                                                                 
//  Problem Statement:                                                                                           
//  You are playing a game against an opponent on a connected ring of nodes 1 ... n where node 1 is connected to 
//  You first get to choose where to start, any node                                                             
//  Then your opponent gets to choose any node where to start                                                    
//                                                                                                               
//  Then you and your opponent alternate turns where you may either capture any node not captured by your opponen
//  Each node has a value given to you                                                                           
//  You each take turns until no one can capture any more nodes                                                  
//  assume your oppoenent plays optimally                                                                        
//                                                                                                               
//  what is the maximum score you can obtain assuming your opponent plays optimally.                             
//                                                                                                               
//                                                                                                               
//                                                                                                               
                                                                                                                 
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 of                            
    //           - 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 );                                                                   
                                                                                                                 
        while (window_min.size() > 0 && window_min.front().first <= index - num_window) 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 - num_window + 1, 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;                             
                                                                                        
        subrange_sum += arr[(i + num_window + N) % N];                                  
        subrange_sum -= arr[i];                                                         
        insert(i + 1, 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_solution(arr) << std::endl;                                      
}                                                                                         

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