Submission #764508

#	Time	Username	Problem	Language	Result	Execution time	Memory
764508		Trunkty	Odd-even (IZhO11_oddeven)	C++14	100 / 100	2 ms	320 KiB

oddeven

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

struct bigint{
    int v[35]={0};
};

int mod = 1e9;

bigint add(bigint a, bigint b){
    bigint c;
    for(int i=0;i<=30;i++){
        c.v[i] += a.v[i]+b.v[i];
        if(c.v[i]>mod){
            c.v[i] -= mod;
            c.v[i+1]++;
        }
    }
    return c;
}

bigint sub(bigint a, bigint b){
    bigint c;
    for(int i=0;i<=30;i++){
        c.v[i] = a.v[i]-b.v[i];
        if(c.v[i]<0){
            c.v[i] += mod;
            a.v[i+1]--;
        }
    }
    return c;
}

bigint mult(bigint a, bigint b){
    bigint c;
    for(int i=0;i<=30;i++){
        for(int j=0;j<=30;j++){
            if(i+j<=30){
                c.v[i+j] += a.v[i]*b.v[j];
                c.v[i+j+1] += c.v[i+j]/mod;
                c.v[i+j] %= mod;
            }
        }
    }
    return c;
}

bool bigeq(bigint a, bigint b){
    for(int i=30;i>=0;i--){
        if(a.v[i]>b.v[i]){
            return true;
        }
        else if(a.v[i]<b.v[i]){
            return false;
        }
    }
    return true;
}

string s;
bigint n,one,two;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    one.v[0] = 1;
    two.v[0] = 2;
    cin >> s;
    reverse(s.begin(),s.end());
    for(int i=s.length()-1;i>=0;i--){
        n.v[i/9] *= 10LL;
        n.v[i/9] += s[i]-'0';
    }
    n = mult(n,two);
    bigint tosub;
    for(int j=14;j>=0;j--){
        int low=0,high=mod-1;
        while(low!=high){
            int mid = (low+high+1LL)/2LL;
            tosub.v[j] = mid;
            if(bigeq(mult(tosub,add(tosub,one)),n)){
                high = mid-1LL;
            }
            else{
                low = mid;
            }
        }
        tosub.v[j] = low;
    }
    tosub = add(tosub,one);
    n = sub(n,tosub);
    bool ld=false;
    for(int i=30;i>=0;i--){
        if(ld){
            string p = to_string(n.v[i]);
            while(p.length()!=9){
                p = "0"+p;
            }
            cout << p;
        }
        else if(n.v[i]>0){
            cout << n.v[i];
            ld = true;
        }
    }
    cout << "\n";
    return 0;
}

• Subtask 1: 100 / 100