Submission #1113485

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113485		duckindog	Line Town (CCO23_day1problem3)	C++17	13 / 25	160 ms	28696 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];

struct BIT { 
  int bit[N];
  inline void upd(int i, int x) { 
    for (; i <= n; i += i & -i) bit[i] += x;
  }
  inline int que(int i) { 
    int ret = 0;
    for (; i; i -= i & -i) ret += bit[i];
    return ret;
  }
} T, Z;

int pref[N];

vector<int> position;

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

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

  int cntZero = 0, totalZero = 0;
  for (int i = 1; i <= n; ++i) {
    if (h[i]) continue;
    position.push_back(i);
    cntZero += 1;
    totalZero += i - 1 - Z.que(i - 1);
    Z.upd(i, 1);
  }
  const int sz = n - cntZero;
  
  int answer = MAX;
  { // the number of 1 is odd
    deque<int> odd, even;
    for (int i = 1; i <= n; ++i) { 
      if (!h[i]) continue;
      auto& vt = (i ^ (h[i] == 1)) & 1 ? odd : even;
      vt.push_back(i);
    }

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

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

      ret += pos - 1 - T.que(pos - 1); 
      ret -= position.end() - upper_bound(position.begin(), position.end(), pos);
      T.upd(pos, 1);
      sequence.push_back(pos);
    }
    
    int total = totalZero;
    { //calculate total
      auto& vt = (n ^ 1) & 1 ? odd : even;
      if (!vt.size()) total = MAX;
      else { 
        int pos = vt.front();
        vt.pop_front();
        total += pos - 1 - T.que(pos - 1) - Z.que(pos - 1);
        sequence.push_back(pos);
      }
    }
    
    if ((int)sequence.size() == sz) {       
      answer = min(answer, pref[sz - 1] + total);
      for (int i = sz - 2; i >= 1; i -= 2) { 
        if (!(cntZero & 1)) swap(sequence[i - 1], sequence[i]);

        T.upd(sequence[i - 1], -1);
        T.upd(sequence[i], -1);

        total += sequence[i - 1] - 1 - T.que(sequence[i - 1] - 1) - Z.que(sequence[i - 1] - 1);
        T.upd(sequence[i - 1], 1);
        
        total += sequence[i] - 1 - T.que(sequence[i] - 1) - Z.que(sequence[i] - 1);
        T.upd(sequence[i], 1);
 
        T.upd(sequence[i - 1], -1);
        T.upd(sequence[i], -1);
        
        answer = min(answer, pref[i - 1] + total);
      }
    }
  }
  
  { // the number of 1 is even
    memset(T.bit, 0, sizeof T.bit);
    deque<int> odd, even;
    for (int i = 1; i <= n; ++i) { 
      if (!h[i]) continue;
      auto& vt = (i ^ (h[i] == 1)) & 1 ? odd : even;
      vt.push_back(i);
    }

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

      auto& vt = i & 1 ? odd : even;
      if (!vt.size()) { ret = MAX; continue; }
      int pos = vt.front();
      vt.pop_front();
      
      ret += pos - 1 - T.que(pos - 1);
      ret -= position.end() - upper_bound(position.begin(), position.end(), pos);
      T.upd(pos, 1);
      sequence.push_back(pos);
    }

    if ((int)sequence.size() == sz) { 
      int total = totalZero;
      answer = min(answer, pref[sz] + total);
      
      for (int i = sz - 1; i >= 1; i -= 2) { 
        if (!(cntZero & 1)) swap(sequence[i - 1], sequence[i]);
        
        T.upd(sequence[i - 1], -1);
        T.upd(sequence[i], -1);

        total += sequence[i - 1] - 1 - T.que(sequence[i - 1] - 1) - Z.que(sequence[i - 1] - 1);
        T.upd(sequence[i - 1], 1);
        
        total += sequence[i] - 1 - T.que(sequence[i] - 1) - Z.que(sequence[i] - 1);
        T.upd(sequence[i], 1);
 
        T.upd(sequence[i - 1], -1);
        T.upd(sequence[i], -1);
        
        answer = min(answer, pref[i - 1] + total);
      }
    }
  }

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

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