# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1108457 | Tsagana | Odd-even (IZhO11_oddeven) | C++14 | 9 ms | 592 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |