oj.uz

Submission #1108457

# Submission time Handle Problem Language Result Execution time Memory
1108457 2024-11-04T07:41:43 Z Tsagana Odd-even (IZhO11_oddeven) C++14
100 / 100
 9 ms 592 KB 
#include<bits/stdc++.h>

#define IOS ios_base::sync_with_stdio(false);cin.tie();cout.tie();
#define all(x) x.begin(), x.end()
#define lnl long long
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

string add_str(string a, string b) {
	string ans;

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

	while (i >= 0 || j >= 0 || c > 0) {
		int d1 = (i >= 0) ? a[i] - '0' : 0;
		int d2 = (j >= 0) ? b[j] - '0' : 0;

		int sum = d1 + d2 + c;

		ans.push_back((sum % 10) + '0');
		c = sum / 10;

		i--; j--;
	}

	reverse(all(ans));
	return ans;
}
string min_str(string a, string b) {
	string ans;
	int i = a.size() - 1;
	int j = b.size() - 1;
	int br = 0;

	while (i >= 0 || j >= 0) {
		int d1 = (i >= 0) ? a[i] - '0' : 0;
		int d2 = (j >= 0) ? b[j] - '0' : 0;

		int diff = d1 - d2 - br;

		if (diff < 0) {
			diff += 10;
			br = 1;
		} else br = 0;

		ans.pb(diff + '0');
		i--; j--;
	}

	while (ans.size() > 1 && ans.back() == '0') {ans.pp();}

	reverse(all(ans));
	return ans;
}
string mul_str(string a, string b) {
	int n = a.size();
	int m = b.size();
	vector<int> ans(n + m, 0);

	for (int i = n - 1; i >= 0; i--) {
		for (int j = m - 1; j >= 0; j--) {
			int mul = (a[i] - '0') * (b[j] - '0');
			int sum = mul + ans[i + j + 1];

			ans[i + j + 1] = sum % 10;
			ans[i + j] += sum / 10;
		}
	}
	
	string anc;
	bool lz = 1;
	for (int d : ans) {
		if (lz && d == 0) continue;
		lz = 0;
		anc.pb(d + '0');
	}
return anc.empty() ? "0" : anc;
}
string div_str(string a, string b) {
	// div by 2
	string ans;
	int c = 0;

	for (char d : a) {
		int curr = c * 10 + (d - '0');
		ans += (curr / 2) + '0';
		c = curr % 2;
	}

	while (ans.size() > 1 && ans[0] == '0') {ans.erase(0, 1);}
	return ans;
}
int	pro_str(string s1, string s2) {
	if (s1.empty() && s2.empty()) return 0;

	if (s1.size() < s2.size()) return 1;
	if (s1.size() > s2.size()) return -1;

	for (size_t i = 0; i < s1.size(); i++) {
		if (s1[i] < s2[i]) return 1;
		if (s1[i] > s2[i]) return -1;
	}
	return 0;
}

string findsquare(string s) {
	if (s == "0" || s == "1") return s;

	string l = "1", r = div_str(s, "2");
	string ans;
	while (pro_str(l, r) != -1) {
		string M = div_str(add_str(l, r), "2");

		string sqr = mul_str(M, M);
		if (!pro_str(sqr, s)) return M;

		if (pro_str(sqr, s) != -1) {
			l = add_str(M, "1");
			ans = M;
		}
		else r = min_str(M, "1");
	}
	return ans;
}

void solve () {
	string n; cin >> n;
	string k = div_str(min_str(findsquare(add_str(mul_str(n, "8"), "1")), "1"), "2");

	string s = mul_str(min_str(n, div_str(mul_str(k, add_str(k, "1")), "2")), "2");
	if (s == "0") {cout << mul_str(k, k); return ;}
	k = min_str(mul_str(k, k), "1");
	cout << add_str(k, s);
}
int main() {IOS solve(); return 0;}

Subtask #1
100.0 / 100.0

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