oj.uz

Submission #913931

# Submission time Handle Problem Language Result Execution time Memory
913931 2024-01-20T14:26:08 Z daoquanglinh2007 Odd-even (IZhO11_oddeven) C++17
100 / 100
 5 ms 600 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 456 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 2 ms 348 KB Output is correct
17 Correct 3 ms 348 KB Output is correct
18 Correct 4 ms 348 KB Output is correct
19 Correct 5 ms 600 KB Output is correct
20 Correct 5 ms 348 KB Output is correct
21 Correct 5 ms 456 KB Output is correct
22 Correct 5 ms 456 KB Output is correct