Submission #1261077

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261077		wheelert	Hacker (BOI15_hac)	C++20	100 / 100	84 ms	10312 KiB

hac

#include <deque>      
#include <iostream>   
#include <queue>      
#include <vector>     
                      
#include <set>        
                      
using namespace std;  
struct SlidingWindowMinimum {                                                      
                                                                                   
  SlidingWindowMinimum(int windowSize) : m_windowSize(windowSize) {}               
                                                                                   
  void observe(int index, int value) {                                             
    // hold values in the queue in increasing order, so the minimum is always at   
    // m_inWindow.front()                                                          
    while (m_inWindow.size() > 0 && m_inWindow.back().second > value)              
      m_inWindow.pop_back();                                                       
                                                                                   
    m_inWindow.push_back({index, value});                                          
  }                                                                                
                                                                                   
  // purge anything less than or equal 'to' from the window                        
  void purge(int to) {                                                             
    while (m_inWindow.size() > 0 && m_inWindow.front().first <= to)                
      m_inWindow.pop_front();                                                      
  }                                                                                
                                                                                   
  void print() const {                                                             
    for (const auto [i, v] : m_inWindow) {                                         
      cout << "(" << i << ", " << v << ") ";                                       
    }                                                                              
    cout << endl;                                                                  
  }                                                                                
                                                                                   
  int min() const { return m_inWindow.front().second; }                            
                                                                                   
  std::deque<std::pair<int, int>> m_inWindow;                                      
  int m_windowSize;                                                                
};                                                                                 
                                                                                   
int optimal_solution(vector<int> const &arr) {                                     
  int N = arr.size();                                                              
  int num_window = (N + 1) / 2;                                                    
                                                                                   
  int winmin_index = 0;                                                            
  SlidingWindowMinimum winmin{num_window};                                         
                                                                                   
  static constexpr int INF = 1'000'000'000;                                        
  vector<int> min_answer_per_node(N + 1, INF);                                     
                                                                                   
  std::vector<int> a(2 * N + 1);                                                   
  for (int i = 1; i <= N; ++i) {                                                   
    a[i] = arr[i - 1];                                                             
    a[i + N] = arr[i - 1];                                                         
  }                                                                                
                                                                                   
  for (int i = 1; i <= 2 * N; ++i)                                                 
    a[i] += a[i - 1];                                                              
                                                                                   
  int ans = 0;                                                                     
  for (int i = 1; i <= 2 * N; ++i) {                                               
    // a[i + num_window -1] - a[i - 1] - computes the sum of elements i ... (i +   
    // num_window - 1) inclusive                                                   
    if (i + num_window - 1 <= 2 * N)                                               
      winmin.observe(i, a[i + num_window - 1] - a[i - 1]);                         
    if (i > num_window)                                                            
      winmin.purge(i - num_window);                                                
                                                                                   
    // mod N but then convert back to 1s based indexing                            
    int prev = ((i - 1) % N) + 1;                                                  
    min_answer_per_node[prev] = min(min_answer_per_node[prev], winmin.min());      
  }                                                                                
  for (int i = 1; i <= N; ++i) {                                                   
    ans = max(ans, min_answer_per_node[i]);                                        
  }                                                                                
                                                                                   
  return ans;                                                                      
}                                                                                  
                                                                                   
// test driver                                                                     
int main() {                                                                       
  int N;                                                                           
  cin >> N;                                                                        
  vector<int> arr(N);                                                              
  for (int i = 0; i < N; ++i)                                                      
    cin >> arr[i];                                                                 
                                                                                   
  std::cout << optimal_solution(arr) << std::endl;                                 
}                                                                                  

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