#include <bits/stdc++.h>
#define vec vector
#define forn(i, s, f) for (int i = s; i <= f; ++i)
#define pb push_back
#define sz(x) (int)((int)(x).size())
#define endl '\n'
using namespace std;
typedef long long ll;
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
typedef pair <int, int> pii;
class BigInt {
private:
static const int base = 1e9;
static const int ss = 9;
vector <int> dig;
int sign = 1;
public:
BigInt () : dig(1, 0), sign(1) {}
BigInt (const int &sign, const vector <int> &dig) : sign(sign), dig(dig) {}
BigInt (const string &s) {
int sh = 0;
if (s[0] == '-') sh = 1, sign = -1;
for (int i = (int)s.size() - ss; i >= sh; i -= ss) {
dig.push_back(stoi(s.substr(i, ss)));
}
if (((int)s.size() - sh) % ss) {
dig.push_back(stoi(s.substr(sh, ((int)s.size() - sh) % ss)));
}
}
void norm ();
BigInt & operator = (const BigInt &other);
friend istream & operator >> (istream &in, BigInt &x);
friend ostream & operator << (ostream &out, const BigInt &x);
bool operator < (const BigInt &other) const;
bool operator > (const BigInt &other) const;
bool operator == (const BigInt &other) const;
bool operator != (const BigInt &other) const;
bool operator <= (const BigInt &other) const;
bool operator >= (const BigInt &other) const;
BigInt operator - () const;
BigInt operator + (const BigInt &other) const;
BigInt operator - (const BigInt &other) const;
BigInt operator * (const BigInt &other) const;
BigInt operator + (const int &x) const;
BigInt operator - (const int &x) const;
BigInt & operator += (const BigInt &other);
BigInt & operator -= (const BigInt &other);
BigInt & operator *= (const BigInt &other);
BigInt & operator += (const int &x);
BigInt & operator -= (const int &x);
BigInt operator * (int x) const;
BigInt operator / (int x) const;
int operator % (const int &x) const;
BigInt & operator *= (const int &x);
BigInt & operator /= (const int &x);
BigInt & operator %= (const int &x);
BigInt & operator ++ ();
};
void BigInt::norm () {
while (!dig.empty() && !dig.back()) dig.pop_back();
if (dig.empty()) dig.push_back(0), sign = 1;
}
BigInt & BigInt::operator = (const BigInt &other) {
dig = other.dig;
sign = other.sign;
return *this;
}
istream & operator >> (istream &in, BigInt &x) {
string s; in >> s;
x = BigInt(s);
return in;
}
ostream & operator << (ostream &out, const BigInt &x) {
if (!~x.sign) out << "-";
char filler = out.fill('0');
cout << x.dig.back();
for (int i = (int)x.dig.size() - 2; i >= 0; --i) {
out << setw(x.ss) << x.dig[i];
}
return out;
}
bool BigInt::operator < (const BigInt &other) const {
if (sign < other.sign) return 1;
if (sign > other.sign) return 0;
if (sign == -1) {
if (dig.size() < other.dig.size()) return 0;
else if (dig.size() > other.dig.size()) return 1;
else {
for (int i = dig.size() - 1; i >= 0; --i) {
if (dig[i] < other.dig[i]) return 0;
if (dig[i] > other.dig[i]) return 1;
}
}
}
else {
if (dig.size() < other.dig.size()) return 1;
else if (dig.size() > other.dig.size()) return 0;
else {
for (int i = dig.size() - 1; i >= 0; --i) {
if (dig[i] < other.dig[i]) return 1;
if (dig[i] > other.dig[i]) return 0;
}
}
}
return 0;
}
bool BigInt::operator > (const BigInt &other) const {
return !(*this <= other);
}
bool BigInt::operator == (const BigInt &other) const {
if (sign != other.sign) return 0;
if (dig.size() != other.dig.size()) return 0;
for (int i = 0; i < dig.size(); ++i) if (dig[i] != other.dig[i]) return 0;
return 1;
}
bool BigInt::operator != (const BigInt &other) const {
return !(*this == other);
}
bool BigInt::operator <= (const BigInt &other) const {
return (*this < other || *this == other);
}
bool BigInt::operator >= (const BigInt &other) const {
return (*this > other || *this == other);
}
BigInt BigInt::operator - () const {
BigInt tm = *this;
tm.sign = -tm.sign;
return tm;
}
BigInt BigInt::operator + (const BigInt &other) const {
if (sign == 1 && other.sign == 1) {
int buf = 0;
BigInt res = (*this);
for (int i = 0; i < other.dig.size() || buf > 0; ++i) {
if (i == res.dig.size()) res.dig.push_back(0);
res.dig[i] += buf + (i < other.dig.size() ? other.dig[i] : 0);
buf = res.dig[i] / base;
res.dig[i] %= base;
}
res.norm();
return res;
}
else if (sign == 1 && other.sign == -1) return (*this - (-other));
else if (sign == -1 && other.sign == -1) return -(-(*this) + (-other));
else if (sign == -1 && other.sign == 1) return -(-(*this) - other);
return BigInt();
}
BigInt BigInt::operator - (const BigInt &other) const {
if (sign == 1 && other.sign == 1) {
if ((*this) < other) return -(other - (*this));
else {
BigInt res = *this;
int buf = 0;
for (int i = 0; i < other.dig.size() || buf > 0; ++i) {
res.dig[i] -= buf + (i < other.dig.size() ? other.dig[i] : 0);
if (res.dig[i] < 0) {
buf = 1; res.dig[i] += base;
}
else buf = 0;
}
res.norm();
return res;
}
}
else if (sign == 1 && other.sign == -1) return ((*this) + (-other));
else if (sign == -1 && other.sign == -1) return -(-(*this) - (-other));
else if (sign == -1 && other.sign == 1) return -(-(*this) + other);
return BigInt();
}
BigInt BigInt::operator * (const BigInt &other) const {
BigInt res;
res.sign = sign * other.sign;
res.dig.resize(dig.size() + other.dig.size());
for (int i = 0; i < dig.size(); ++i) {
if (!dig[i]) continue;
int buf = 0;
for (int j = 0; j < other.dig.size() || buf; ++j) {
long long ml = res.dig[i + j] + buf + dig[i] * 1ll * (j < other.dig.size() ? other.dig[j] : 0);
res.dig[i + j] = ml % base;
buf = ml / base;
}
}
res.norm();
return res;
}
BigInt BigInt::operator + (const int &x) const {
return (*this) + BigInt(to_string(x));
}
BigInt BigInt::operator - (const int &x) const {
return (*this) + (-x);
}
BigInt & BigInt::operator += (const BigInt &other) {
*this = *this + other;
return *this;
}
BigInt & BigInt::operator -= (const BigInt &other) {
*this = *this - other;
return *this;
}
BigInt & BigInt::operator *= (const BigInt &other) {
(*this) = (*this) * other;
return *this;
}
BigInt BigInt::operator * (int x) const {
BigInt res = (*this);
res.sign *= (x < 0 ? -1 : 1);
x *= (x < 0 ? -1 : 1);
int buf = 0;
for (int i = 0; i < res.dig.size() || buf > 0; ++i) {
if (i == res.dig.size()) res.dig.push_back(0);
long long ml = buf + res.dig[i] * 1ll * x;
res.dig[i] = ml % base;
buf = ml / base;
}
res.norm();
return res;
}
BigInt BigInt::operator / (int x) const {
vector <int> d = this -> dig;
reverse(d.begin(), d.end());
BigInt res;
res.sign = ((this -> sign) * (x < 0 ? -1 : 1));
x = abs(x);
long long s = 0, uk = 0;
while (uk < d.size() && s < x) {
s *= (this -> base); s += d[uk++];
}
while (uk < d.size()) {
res.dig.push_back(s / x);
s %= x; s *= (this -> base); s += d[uk++];
}
res.dig.push_back(s / x);
reverse(res.dig.begin(), res.dig.end()); res.norm();
return res;
}
int BigInt::operator % (const int &x) const {
vector <int> d = this -> dig;
reverse(d.begin(), d.end());
long long s = 0, uk = 0;
while (uk < d.size() && s < x) {
s *= (this -> base); s += d[uk++];
}
while (uk < d.size()) {
s %= x; s *= (this -> base); s += d[uk++];
}
s %= x;
if (!~sign) s = (x - s);
return s;
}
BigInt & BigInt::operator *= (const int &x) {
(*this) = (*this) * x;
return *this;
}
BigInt & BigInt::operator /= (const int &x) {
(*this) = (*this) / x;
return *this;
}
BigInt & BigInt::operator %= (const int &x) {
(*this) = BigInt(to_string((*this) % x));
return *this;
}
BigInt & BigInt::operator ++ () {
(*this) = (*this) + 1;
return (*this);
}
inline void solve () {
string s; cin >> s;
BigInt q (s);
BigInt w ("1");
BigInt G = q * 8 - 7;
BigInt ONE ("1");
BigInt l ("1"), r (string(101, '9'));
while (r - l > ONE) {
BigInt mid = l + r; mid /= 2;
if (mid * mid > G) r = mid;
else l = mid;
}
r /= 2;
cout << q * 2 - r << endl;
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
#endif
int t = 1; //cin >> t;
while (t--) solve();
return 0;
}
Compilation message
oddeven.cpp: In constructor 'BigInt::BigInt(const int&, const std::vector<int>&)':
oddeven.cpp:21:21: warning: 'BigInt::sign' will be initialized after [-Wreorder]
21 | int sign = 1;
| ^~~~
oddeven.cpp:20:30: warning: 'std::vector<int> BigInt::dig' [-Wreorder]
20 | vector <int> dig;
| ^~~
oddeven.cpp:24:17: warning: when initialized here [-Wreorder]
24 | BigInt (const int &sign, const vector <int> &dig) : sign(sign), dig(dig) {}
| ^~~~~~
oddeven.cpp: In function 'std::ostream& operator<<(std::ostream&, const BigInt&)':
oddeven.cpp:92:14: warning: unused variable 'filler' [-Wunused-variable]
92 | char filler = out.fill('0');
| ^~~~~~
oddeven.cpp: In member function 'bool BigInt::operator==(const BigInt&) const':
oddeven.cpp:130:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
130 | for (int i = 0; i < dig.size(); ++i) if (dig[i] != other.dig[i]) return 0;
| ~~^~~~~~~~~~~~
oddeven.cpp: In member function 'BigInt BigInt::operator+(const BigInt&) const':
oddeven.cpp:152:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for (int i = 0; i < other.dig.size() || buf > 0; ++i) {
| ~~^~~~~~~~~~~~~~~~~~
oddeven.cpp:153:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | if (i == res.dig.size()) res.dig.push_back(0);
| ~~^~~~~~~~~~~~~~~~~
oddeven.cpp:154:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | res.dig[i] += buf + (i < other.dig.size() ? other.dig[i] : 0);
| ~~^~~~~~~~~~~~~~~~~~
oddeven.cpp: In member function 'BigInt BigInt::operator-(const BigInt&) const':
oddeven.cpp:172:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
172 | for (int i = 0; i < other.dig.size() || buf > 0; ++i) {
| ~~^~~~~~~~~~~~~~~~~~
oddeven.cpp:173:56: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | res.dig[i] -= buf + (i < other.dig.size() ? other.dig[i] : 0);
| ~~^~~~~~~~~~~~~~~~~~
oddeven.cpp: In member function 'BigInt BigInt::operator*(const BigInt&) const':
oddeven.cpp:192:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | for (int i = 0; i < dig.size(); ++i) {
| ~~^~~~~~~~~~~~
oddeven.cpp:195:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
195 | for (int j = 0; j < other.dig.size() || buf; ++j) {
| ~~^~~~~~~~~~~~~~~~~~
oddeven.cpp:196:81: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
196 | long long ml = res.dig[i + j] + buf + dig[i] * 1ll * (j < other.dig.size() ? other.dig[j] : 0);
| ~~^~~~~~~~~~~~~~~~~~
oddeven.cpp: In member function 'BigInt BigInt::operator*(int) const':
oddeven.cpp:230:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
230 | for (int i = 0; i < res.dig.size() || buf > 0; ++i) {
| ~~^~~~~~~~~~~~~~~~
oddeven.cpp:231:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
231 | if (i == res.dig.size()) res.dig.push_back(0);
| ~~^~~~~~~~~~~~~~~~~
oddeven.cpp: In member function 'BigInt BigInt::operator/(int) const':
oddeven.cpp:246:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
246 | while (uk < d.size() && s < x) {
| ~~~^~~~~~~~~~
oddeven.cpp:249:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
249 | while (uk < d.size()) {
| ~~~^~~~~~~~~~
oddeven.cpp: In member function 'int BigInt::operator%(const int&) const':
oddeven.cpp:261:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
261 | while (uk < d.size() && s < x) {
| ~~~^~~~~~~~~~
oddeven.cpp:264:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
264 | while (uk < d.size()) {
| ~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
320 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
312 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
324 KB |
Output is correct |
| 13 |
Correct |
1 ms |
212 KB |
Output is correct |
| 14 |
Correct |
1 ms |
212 KB |
Output is correct |
| 15 |
Correct |
1 ms |
316 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
1 ms |
320 KB |
Output is correct |
| 18 |
Correct |
1 ms |
316 KB |
Output is correct |
| 19 |
Correct |
1 ms |
316 KB |
Output is correct |
| 20 |
Correct |
1 ms |
320 KB |
Output is correct |
| 21 |
Correct |
1 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
212 KB |
Output is correct |
