Submission #18976874

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
#define x first
#define y second
#define bg begin()
#define ed end()
#define pb push_back
#define mp make_pair
#define sz(a) int((a).size())
#define R(i,n) for(int i(0);i<(n);++i)
#define L(i,n) for(int i((n)-1);i>=0;--i)
const int iinf=0x3f3f3f3f;
const ll linf=0x3f3f3f3f3f3f3f3f;

//Data
const int N=5e5+2;
int n,a[N],b[N];
string str;

//Function
bool coback(bool res){
    R(i,n) a[i]=b[i];
    // cout<<"res="<<res<<'\n';
    return res;
}
bool check(int m){
    // cout<<"checking:"<<m<<'\n';
    R(i,n) b[i]=a[i];
    int x=m*9;
    R(i,n){
        if(a[i]<0){
            int inc=(abs(a[i])+9)/10;
            if(inc&&i==n-1) return coback(true);
            a[i+1]-=inc,a[i]+=inc*10;
        }
        if(a[i]<=x%10) x+=a[i]-x%10;
        else x+=a[i]-x%10-10;
        if(x<0) return coback(false);
        if(x/10&&i==n-1) return coback(true);
        a[i]-=x%10,a[i+1]-=x/10;
    }
    return coback(true);
}

//Main
int main(){
    // freopen("AGC011E.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    // cout<<"i love fyy\n";
    cin>>str,n=sz(str);
    R(i,n) a[i]=str[n-1-i]-='0';
    // cout<<"mobaizhouayang\n";
    int l=0,r=n<<1;
    while(r-l>1){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid;
    }
    cout<<r<<'\n';
    return 0;
}

Submission Info

Judge Result