#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
using namespace std;
void debug(string names) {
cout << '\n';
}
template<typename A1, typename... A2>
void debug(string names, A1 par, A2... left) {
int pos = 0;
for (; pos < names.size() && names[pos] != ' ' && names[pos] != ','; pos++)
cout << names[pos];
cout << ": " << par << " ";
while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) {
pos++;
}
names.erase(names.begin(), names.begin() + pos);
debug(names, left...);
}
struct bigint {
const int lim = 10000, g = 4;
vector<int> a;
bigint() {
a.clear();
}
bigint(string s) {
a.clear();
reverse(s.begin(), s.end());
for (int i = 0; i < s.size(); i += g) {
a.push_back(0);
for (int j = min((int)s.size() - 1, i + g - 1); j >= i; j--) {
a.back() = 10 * a.back() + (s[j] - '0');
}
}
}
bigint(int val) {
a.clear();
while (val) {
a.push_back(val % lim);
val /= lim;
}
}
bigint(vector<int> &b) {
a = b;
}
bigint(vector<ll> &b) {
a.clear();
a.resize(b.size());
for (int i = 0; i < b.size(); i++) a[i] = b[i];
}
void clear(vector<ll> &b) const {
ll rem = 0;
for (auto &i : b) {
i += rem;
rem = i / lim;
i %= lim;
}
while (rem) {
b.push_back(rem % lim);
rem /= lim;
}
}
void clear(vector<int> &b) const {
int rem = 0;
for (auto &i : b) {
i += rem;
rem = i / lim;
i %= lim;
}
while (rem) {
b.push_back(rem % lim);
rem /= lim;
}
}
void clear() {
clear(this->a);
}
bigint operator + (const bigint &x) const {
vector<int> b;
for (int i = 0; i < x.a.size() || i < a.size(); i++) {
b.push_back(0);
if (i < x.a.size()) b[i] += x.a[i];
if (i < a.size()) b[i] += a[i];
}
clear(b);
return bigint(b);
}
bigint operator + (int val) const {
bigint b(val);
return *this + b;
}
bigint operator - (const bigint &x) const {
bigint b = *this;
int sub = 0;
for (int i = 0; i < b.a.size(); i++) {
b.a[i] -= sub; sub = 0;
if (i < x.a.size()) b.a[i] -= x.a[i];
if (b.a[i] < 0) {
b.a[i] += lim;
sub = 1;
}
}
while (b.a.size() && b.a.back() == 0) b.a.pop_back();
return b;
}
bigint operator - (int val) const {
bigint b(val);
return *this - b;
}
bigint operator * (const bigint &x) const {
vector<ll> b((int)this->a.size() + (int)x.a.size() - 1);
for (int i = 0; i < a.size(); i++) for (int j = 0; j < x.a.size(); j++)
b[i + j] += a[i] * x.a[j];
clear(b);
return bigint(b);
}
bigint operator * (int val) const {
bigint b(val);
return *this * b;
}
bigint operator / (int val) const {
bigint b = *this;
ll add = 0;
for (int i = (int)b.a.size() - 1; i >= 0; i--) {
b.a[i] += add * lim;
add = b.a[i] % val;
b.a[i] /= val;
}
while (b.a.size() && b.a.back() == 0) b.a.pop_back();
clear(b.a);
return b;
}
void operator = (bigint x) {
a = x.a;
}
bool operator < (const bigint &x) const {
if (a.size() != x.a.size()) return a.size() < x.a.size();
for (int i = (int)a.size() - 1; i >= 0; i--) {
if (a[i] != x.a[i]) return a[i] < x.a[i];
}
return false;
}
void print() {
if (a.size() == 0) return;
cout << a.back();
int tmp;
for (int i = (int)a.size() - 2; i >= 0; i--) {
tmp = lim / 10;
while (tmp) {
cout << (a[i] / tmp) % 10;
tmp /= 10;
}
}
}
};
string s;
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> s;
bigint n(s);
n = n * 2;
bigint lo("0"), hi = n, mid, tmp;
while (lo < hi) {
mid = (lo + hi + 1) / 2;
tmp = mid + 1;
if (mid * tmp < n) lo = mid;
else hi = mid - 1;
}
bigint ans = n - lo - 1;
ans.print();
}
Compilation message
oddeven.cpp: In constructor 'bigint::bigint(std::__cxx11::string)':
oddeven.cpp:34:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < s.size(); i += g) {
~~^~~~~~~~~~
oddeven.cpp: In constructor 'bigint::bigint(std::vector<long long int>&)':
oddeven.cpp:54:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < b.size(); i++) a[i] = b[i];
~~^~~~~~~~~~
oddeven.cpp: In member function 'bigint bigint::operator+(const bigint&) const':
oddeven.cpp:85:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < x.a.size() || i < a.size(); i++) {
~~^~~~~~~~~~~~
oddeven.cpp:85:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < x.a.size() || i < a.size(); i++) {
~~^~~~~~~~~~
oddeven.cpp:87:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i < x.a.size()) b[i] += x.a[i];
~~^~~~~~~~~~~~
oddeven.cpp:88:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i < a.size()) b[i] += a[i];
~~^~~~~~~~~~
oddeven.cpp: In member function 'bigint bigint::operator-(const bigint&) const':
oddeven.cpp:100:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < b.a.size(); i++) {
~~^~~~~~~~~~~~
oddeven.cpp:102:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i < x.a.size()) b.a[i] -= x.a[i];
~~^~~~~~~~~~~~
oddeven.cpp: In member function 'bigint bigint::operator*(const bigint&) const':
oddeven.cpp:117:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.size(); i++) for (int j = 0; j < x.a.size(); j++)
~~^~~~~~~~~~
oddeven.cpp:117:56: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.size(); i++) for (int j = 0; j < x.a.size(); j++)
~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
380 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
2 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
2 ms |
376 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
2 ms |
376 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
2 ms |
376 KB |
Output is correct |
| 16 |
Correct |
2 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
3 ms |
376 KB |
Output is correct |
| 19 |
Correct |
3 ms |
376 KB |
Output is correct |
| 20 |
Correct |
3 ms |
376 KB |
Output is correct |
| 21 |
Correct |
3 ms |
376 KB |
Output is correct |
| 22 |
Correct |
3 ms |
376 KB |
Output is correct |
