Submission #1113427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113427		duckindog	Line Town (CCO23_day1problem3)	C++17	9 / 25	2053 ms	21800 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];

namespace sub2 { 
  int pref[N];
  void solve() { 
    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";
  }
}

namespace sub3 { 
  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;
  }

  void solve() { 
    int cntZero = 0;
    for (int i = 1; i <= n; ++i) { 
      if (!h[i]) cntZero += 1;
    }

    int answer = MAX;
    for (int negNum = 0; negNum <= n - cntZero; ++negNum) { 
      auto cal = [&]() { 
        deque<int> odd, even;
        for (int i = 1; i <= n; ++i) { 
          if (h[i]) { 
            auto& vt = ((i ^ (h[i] == 1)) & 1) ? odd : even;
            vt.push_back(i);
          }
        }

        memset(bit, 0, sizeof bit);
        int ret = 0;
        for (int i = 1; i <= negNum; ++i) { 
          auto& vt = i & 1 ? odd : even;
          
          if (!vt.size()) return MAX;
          ret += vt.front() - 1 - que(vt.front() - 1);
          upd(vt.front(), 1);
           
          vt.pop_front();
        }
        for (int i = 1; i <= n; ++i) {
          if (h[i]) continue;
          ret += i - 1 - que(i - 1);
          upd(i, 1);
        }
        for (int i = negNum + cntZero + 1; i <= n; ++i) { 
          auto& vt = (i ^ 1) & 1 ? odd : even;
          
          if (!vt.size()) return MAX;
          ret += vt.front() - 1 - que(vt.front() - 1);
          upd(vt.front(), 1);
          
          vt.pop_front();
        }
        
        return ret;
      };

      answer = min(answer, cal());
    }

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

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

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

  if (all_of(h + 1, h + n + 1, [](const auto& a) { return abs(a) == 1; })) {
    sub2::solve();
    return 0;
  }

  if (all_of(h + 1, h + n + 1, [](const auto& a) { return abs(a) <= 1; })) {
    sub3::solve();
    return 0;
  }
  
  assert(false);
}

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