Submission #1113323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113323		duckindog	Line Town (CCO23_day1problem3)	C++17	6 / 25	55 ms	21632 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 500'000 + 10,
          MAX = 1'000'000'000'000'000;
int n;
int h[N];

int pref[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for (int i = 1; i <= n; ++i) cin >> h[i];

  int answer = MAX;  
  { // the number of 1 is odd
    deque<int> odd, even;
    for (int i = 1; i <= n; ++i) { 
      auto& vt = (i ^ (h[i] == 1)) & 1 ? odd : even;
      vt.push_back(i);
    }

    vector<int> sequence;
    for (int i = 1; i < n; ++i) { 
      auto& ret = pref[i];
      ret = pref[i - 1];

      auto& vt = i & 1 ? odd : even;
      if (!vt.size()) { ret = MAX; continue; }

      sequence.push_back(vt.front());
      ret += max(0ll, i - vt.front());
      vt.pop_front();
    }

    if (pref[n - 1] < MAX) { 
      answer = min(answer, pref[n - 1]);
      
      int total = 0;      
      { // i == n
        int i = n;

        auto& ret = pref[i];
        ret = pref[i - 1];

        auto& vt = (i ^ 1) & 1 ? odd : even;
        if (!vt.size()) ret = MAX;

        sequence.push_back(vt.front());
        ret += max(0ll, i - vt.front());
        total += max(0ll, i - vt.front());
        vt.pop_front();
      }
      
      for (int i = n - 2; i >= 1; i -= 2) { 
        swap(sequence[i - 1], sequence[i]);

        total += max(0ll, i - sequence[i - 1]);
        total += max(0ll, i + 1 - sequence[i]);
        
        answer = min(answer, pref[i - 1] + total);
      }
    }
  }
  
  { // the number of 1 is even
    deque<int> odd, even;
    for (int i = 1; i <= n; ++i) { 
      auto& vt = (i ^ (h[i] == 1)) & 1 ? odd : even;
      vt.push_back(i);
    }

    vector<int> sequence;
    for (int i = 1; i <= n; ++i) { 
      auto& ret = pref[i];
      ret = pref[i - 1];

      auto& vt = i & 1 ? odd : even;
      if (!vt.size()) { ret = MAX; continue; }

      sequence.push_back(vt.front());
      ret += max(0ll, i - vt.front());
      vt.pop_front();
    }
    
    if (pref[n] < MAX) { 
      answer = min(answer, pref[n]);
      
      int total = 0;
      for (int i = n - 1; i >= 1; i -= 2) { 
        swap(sequence[i - 1], sequence[i]);

        total += max(0ll, i - sequence[i - 1]);
        total += max(0ll, i + 1 - sequence[i]);

        answer = min(answer, pref[i - 1] + total);
      }
    }
  }

  cout << (answer == MAX ? -1 : answer) << "\n";
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 0 / 3
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 3
• Subtask 7: 0 / 2
• Subtask 8: 0 / 3