Submission #879809

#	Time	Username	Problem	Language	Result	Execution time	Memory
879809		Elvin_Fritl	Odd-even (IZhO11_oddeven)	C++17	100 / 100	10 ms	444 KiB

oddeven

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

#define io                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);


typedef long long ll;

ll bp(ll n,ll m){
    if(m == 0){
        return 1;
    }
    if(m == 1){
        return n;
    }
    if(m%2==0){
        return bp(n*n,m/2);
    }
    return n*bp(n,m-1);
}


const int N =  1e6 + 545, M = 33, inf = 1e9 + 99;
const ll inff = 1e12;

string sum(string a,string b) {
	string res;
    int tmp = 0;

    int i = a.size() - 1 , j = b.size() - 1;

    while (i >= 0 || j >= 0 || tmp > 0) {
        int fi = (i >= 0) ? (a[i] - '0') : 0  ,  se = (j >= 0) ? (b[j] - '0') : 0;

        int sum = fi + se + tmp;
        tmp = sum / 10;

        res.push_back((sum % 10) + '0');

        --i;
        --j;
    }

    reverse(res.begin(), res.end());

    return res;
}

string div(string a) {
    string res;
    int tmp = 0;

    for (int i = 0; i <(int)a.size(); ++i) {
        tmp = tmp * 10 + (a[i] - '0');

        if(tmp/2 == 0) {
            if (!res.empty()) {
                res += '0';
            }
        }
        else {
            res += to_string(tmp / 2);
            tmp %= 2;
        }
    }

    return res;
}

string mul(string a, string b) {
    int m = a.size() , n = b.size();
    string res(m + n, '0');

    for(int i=m-1;i>=0;i--) {
        int tmp = 0;
        for(int j=n-1;j>=0;j--) {
            int cur = (a[i] - '0') * (b[j] - '0') + (res[i + j + 1] - '0') + tmp;
            res[i + j + 1] = cur % 10 + '0';
            tmp = cur / 10;
        }
        res[i] += tmp;
    }

    size_t it = res.find_first_not_of('0');
    if (it != std::string::npos) {
        return res.substr(it);
    }

    return "0";
}

string sub(string a, string b) {
    int m = a.size() , n = b.size();
    string res(max(m, n), '0');

    int tmp = 0;
    for(int i=0;i<max(m, n);i++) {
        int fi = (i < m) ? (a[m - 1 - i] - '0') : 0 , se = (i < n) ? (b[n - 1 - i] - '0') : 0;

        int cur = fi - se - tmp;
        if(cur < 0) {
            cur += 10;
            tmp = 1;
        }
        else {
            tmp = 0;
        }

        res[res.size() - 1 - i] = cur + '0';
    }

    size_t it = res.find_first_not_of('0');
    if (it != std::string::npos) {
        return res.substr(it);
    }

    return "0";
}

bool chek(string a,string b) {
	if(a.size() < b.size()) {
		return false;
	}
	if(a.size() > b.size()) {
		return true;
	}
	for(int i=0;i<(int)a.size();i++) {
		if(a[i] > b[i]) {
			return true;
		}
		if(a[i] < b[i]) {
			return false;
		}
	}
	return true;
}

int main() {

	string n;
	cin >> n;
    string l = "1" , r = n, res = "-1";
    while(chek(r , l) == true) {
        string mid = sum(l , r);
        ///cerr << mid << endl;
        mid = div(mid);
        ///cerr << l << "         " << r << "            " << mid << endl;
        string fi = sum(mid , "1");
        string se = mul(mid , fi);
        string th = div(se);
        ///cerr << fi << "    || " << se << "          ||   " << th << endl;
        if(chek(th , n)) {
          	res = mid;
			r = sub(mid , "1");
		}
        else {
                ///cerr << l << "       ";
			l = sum(mid , "1");
                ///cerr << l << "       \n";
		}
	}
	string tmp =  mul("2" , n);
	///cerr << tmp << "   " << res << endl;
	if(res == "-1") {
		cout << sum(tmp , "1") << endl;
		return 0;
	}
    cout << sub(tmp, res);

}
/*
1 2 4 5 7 9 10 12 14 16 17 19 21 23 25 16 18 30 32 34 36
*/

• Subtask 1: 100 / 100