結果

問題 No.3114 0→1
ユーザー moti
提出日時 2025-04-19 20:08:08
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,538 bytes
コンパイル時間 1,062 ms
コンパイル使用メモリ 135,424 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-19 20:08:11
合計ジャッジ時間 2,554 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <sstream>
#include <cassert>

using namespace std;

void debug(const string &S, int left, int right, int cnt) {
  /*
  string visualized = S.substr(left, right - left);
  string markers = string(left, ' ') + "^" + string(right - left - 1, ' ') + "^";
  cout << S << endl;
  cout << markers << endl;
  cout << "Substring: " << visualized << " - Count: " << cnt << endl;
  */
}

int main() {
  int N;
  string S;
  cin >> N >> S;
  int cnt = 0;
  int left = 0, right = 1;
  int ans = 0;
  for (; right < N + 1; right++) {
    if (S[right - 1] == '0') cnt--;
    else cnt++;
    debug(S, left, right, cnt);
    if (right - left >= 2) {
      if (cnt < 0) {
        assert(S[right - 1] == '0');
        S[right - 1] = '1';
        cnt += 2;
        ans++;
        debug(S, left, right, cnt);
        int i = 1;
        while (left < right - 1) {
          if (S[left] == '0') cnt++;
          else cnt--;
          left++;
          debug(S, left, right, cnt);
          if (cnt < 0) {
            bool fixed = false;
            for (int j = right - i - 1; j > left; j--, i++) {
              if (S[j] == '0') {
                S[j] = '1';
                cnt += 2;
                ans++;
                debug(S, left, right, cnt);
                fixed = true;
                i++;
                break;
              }
            }
            assert(fixed);            
          }
        }
      }
    }
  }
  cout << ans << endl;
}
0