結果

問題 No.3266 岩井星人は見ずにはいられない
コンテスト
ユーザー shingo0909
提出日時 2025-09-06 15:37:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 185 ms / 2,000 ms
コード長 1,159 bytes
コンパイル時間 3,680 ms
コンパイル使用メモリ 284,412 KB
実行使用メモリ 199,064 KB
最終ジャッジ日時 2025-09-06 15:38:01
合計ジャッジ時間 8,629 ms
ジャッジサーバーID
（参考情報） 		judge / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <cstdlib>
#include <math.h>
using namespace std;

using ll = long long;


int main(){
    ll n,a;
    cin >> n >> a;
    string s;
    cin >> s;
    vector p(41,vector<int>(2*n,0));
    vector l(41,vector<ll>(2*n,0));
    int c0=0;
    int c1=0;
    int x=0;
    for(char c:s){
        if(c=='0')c0++;
        else{
            c1++;
            x=max(c1-c0,x);
        }
    }
    for(int i=0;i<2*n;i++){
        p[0][i]=min(ll(i+c0-c1+max(x-i,0)),2*n-1);
        l[0][i]=c1-max(x-i,0);
    }
    for(int i=0;i<40;i++){
        for(int j=0;j<2*n;j++){
            p[i+1][j]=p[i][p[i][j]];
            l[i+1][j]=l[i][j]+l[i][p[i][j]];
        }
    }
    ll now=0;
    ll ac=0;
    ll ans=0;
    for(int i=40;i>=0;i--){
        if(l[i][now]+ac>=a)continue;
        ac+=l[i][now];
        now=p[i][now];
        ans+=n<<i;
    }
    for(int i=0;i<n;i++){
        if(s[i]=='0')now++;
        else{
            if(now==0)continue;
            else {
                now--;
                ac++;
            }
        }
        if(ac==a){
            cout << ans+i+1 << endl;
            return 0;
        }
    }
    return 0;
}
0