Submission #913931

#	Time	Username	Problem	Language	Result	Execution time	Memory
913931		daoquanglinh2007	Odd-even (IZhO11_oddeven)	C++17	100 / 100	5 ms	600 KiB

oddeven

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

#define all(a) a.begin(), a.end()
#define isz(a) (int)(a).size()

string S;

int cmp(string a, string b){
	if (isz(a) < isz(b)) return -1;
	if (isz(a) > isz(b)) return 1;
	if (a < b) return -1;
	if (a > b) return 1;
	return 0;
}

string add(string a, string b){
	reverse(all(a));
	reverse(all(b));
	while (isz(a) < isz(b)) a.push_back('0');
	while (isz(b) < isz(a)) b.push_back('0');
	string c = "";
	int carry = 0;
	for (int i = 0; i < isz(a); i++){
		int s = a[i]+b[i]-2*'0'+carry;
		c.push_back(s%10+'0');
		carry = s/10;
	}
	if (carry) c.push_back('1');
	reverse(all(c));
	return c;
}

string sub(string a, string b){
	reverse(all(a));
	reverse(all(b));
	while (isz(a) < isz(b)) a.push_back('0');
	while (isz(b) < isz(a)) b.push_back('0');
	string c = "";
	int borrow = 0;
	for (int i = 0; i < isz(a); i++){
		int h = a[i]-b[i]-borrow;
		if (h < 0){
			borrow = 1;
			h += 10;
		}
		else borrow = 0;
		c.push_back(h+'0');
	}
	while (isz(c) > 1 && c[isz(c)-1] == '0') c.erase(isz(c)-1, 1);
	reverse(all(c));
	return c;
}

string mul(string a, string b){
	reverse(all(a));
	reverse(all(b));
	string c = "";
	for (int i = 0; i < isz(a)+isz(b); i++) c.push_back('0');
	
	for (int i = 0; i < isz(a); i++){
		int carry = 0;
		for (int j = 0; j < isz(b); j++){
			int s = (a[i]-'0')*(b[j]-'0')+(c[i+j]-'0')+carry;
			c[i+j] = s%10+'0';
			carry = s/10;
		}
		c[i+isz(b)] = carry+'0';
	}
	
	while (isz(c) > 1 && c[isz(c)-1] == '0') c.erase(isz(c)-1, 1);
	reverse(all(c));
	return c;
}

string div(string a, int b){
	string c = "";
	int h = 0;
	for (int i = 0; i < isz(a); i++){
		h = h*10+a[i]-'0';
		c.push_back(h/b+'0');
		h %= b;
	}
	reverse(all(c));
	while (isz(c) > 1 && c[isz(c)-1] == '0') c.erase(isz(c)-1, 1);
	reverse(all(c));
	return c;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> S;
	string L = "1", R = S, res = "0";
	while (cmp(L, R) <= 0){
		string mid = div(add(L, R), 2);
		if (cmp(div(mul(mid, add(mid, "1")), 2), S) >= 0){
			res = mid;
			R = sub(mid, "1");
		}
		else{
			L = add(mid, "1");
		}
	}
	cout << sub(mul(S, "2"), res);
	return 0;
}

• Subtask 1: 100 / 100