結果

問題 No.1437 01 Sort
ユーザー tyawanmusi
提出日時 2021-02-21 01:35:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 761 ms / 2,000 ms
コード長 3,481 bytes
コンパイル時間 3,130 ms
コンパイル使用メモリ 207,268 KB
最終ジャッジ日時 2025-01-19 02:55:04
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using Graph = vector<vector<ll>>;
using Graph_c = vector<vector<pll>>;
#define INF32 2147483647LL
#define INF 9223372036854775807LL
#define all(x) x.begin(), x.end()
#define len(x) (ll) x.size()
#define name2(i, a, b, c, ...) c
#define name3(i, a, b, c, d, ...) d
#define name4(i, a, b, c, d, e, ...) e
#define rep(...) name3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define rep1(i, a) for(ll i = 0, a_sub = a; i < a_sub; i++)
#define rep2(i, a, b) for(ll i = a, b_sub = b; i < b_sub; i++)
#define rep3(i, a, b, c) for(ll i = a, a_sub = a, b_sub = b, c_sub = c; (a_sub <= i && i < b_sub) or (a_sub >= i && i > b_sub); i += c_sub)
#define each(...) name4(__VA_ARGS__, each4, each3, each2, each1)(__VA_ARGS__)
#define each1(i, a) for(auto i : a)
#define each2(i, j, a) for(auto [i, j] : a)
#define each3(i, j, k, a) for(auto [i, j, k] : a)
#define each4(i, j, k, l, a) for(auto [i, j, k, l] : a)
#define sum(...) name2(__VA_ARGS__, sum2, tmp, sum1)(__VA_ARGS__)
#define sum1(a) accumulate(all(a), 0LL)
#define sum2(a, l, r) accumulate(a.begin() + l, a.begin() + min(r, len(a)), 0LL)
#define pb push_back
vector<pll> dxy4 = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
vector<pll> dxy8 = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  ll n, ans = INF;
  string s;
  cin >> n >> s;
  
  ll zero = 0, one = 0;
  vector<ll> bit;
  rep(i, n) {
    if(s[i] == '0')
      zero++;
    else {
      one++;
      bit.pb(i);
      bit.pb(i + n);
      bit.pb(i + n + n);
    }
  }
  sort(all(bit));

  if(zero == n or zero == 0) {
    cout << 0 << endl;
    return 0;
  }

  vector<bool> out(n, true);
  if(s[0] == '1') {
    out[0] = false;
    rep(i, n - 1, -1, -1) {
      if(s[i] == '1')
        out[i] = false;
      else
        break;
    }
  }

  auto f = [n, one, bit, out](ll l1, ll l2) {
    ll sp_l = (l1 + one) % n, sp_r = n;
    if(sp_l == 0) sp_l = n;

    ll ansl = 0, ansr = 0;

    if(bit[l2] <= l1 + n) {
      if(sp_l <= (bit[l2] + n - 1) % n + 1 and (bit[l2] + n - 1) % n + 1 <= sp_r and out[bit[l2] % n])
        ansl = l1 + n - bit[l2] - 1;
      else
        ansl = l1 + n - bit[l2];
    }

    if(l1 + n + one - 1 < bit[l2 + one - 1]) {

      ll ng = -1, ok = one;
      while(ng + 1 != ok) {
        ll mid = (ng + ok) / 2;
        if(l1 + n + mid < bit[l2 + mid])
          ok = mid;
        else
          ng = mid;
      }

      bool flag1 = true, flag2 = false;
      ll x = l1 + n + ok;
      if(x % n) x += n - (x % n);
      if(x <= l1 + n + one - 1) {
        if(l1 + n + ok <= bit[l2 + ok] and bit[l2 + ok] <= x) flag2 = true;
        x += n;
      }
      if(l1 + n + ok <= bit[l2 + ok] and bit[l2 + ok] <= x) flag1 = false;
      ansr = one - ok;
      ansr += flag1;
      ansr -= flag2;
    }

    return max(ansl, ansr);
  };

  rep(l1, n) {
    ll anss = (n + n - l1 - one) % n, sp_l = (l1 + one) % n, sp_r = n;
    if(sp_l == 0) sp_l = n;

    ll ng = -1, ok = n;
    while(ng + 1 != ok) {
      ll mid = (ng + ok) / 2;
      
      ll x = l1 + n - mid - 1;
      if(not(sp_l <= (x + n - 1) % n + 1 and (x + n - 1) % n + 1 <= sp_r and out[x % n])) x++;
      ll l2 = lower_bound(all(bit), x) - bit.begin();
      
      if(f(l1, l2) <= mid)
        ok = mid;
      else
        ng = mid;
    }

    ans=min(ans,anss+ok*n);
  }
  cout<<ans<<endl;
}
0