#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }
class BigInt {
private:
static const int base = 1e9;
static const int len = 9;
bool sgn; // 1 - pos, 0 - neg
vector <int> dig;
void normalize();
BigInt babs() const {
return sgn ? *this : -*this;
};
public:
BigInt() {}
BigInt(const int &);
BigInt(const string &);
bool operator < (const BigInt &) const;
bool operator == (const BigInt &) const;
bool operator > (const BigInt &) const;
friend istream & operator >> (istream &, BigInt &);
friend ostream & operator << (ostream &, const BigInt &);
BigInt operator + (const BigInt &) const;
BigInt& operator++ (int);
BigInt operator * (const BigInt &) const;
BigInt operator * (const int &) const;
friend BigInt operator - (const BigInt &);
BigInt operator - (const BigInt &) const;
BigInt operator / (const int &) const;
int operator % (const int &) const;
};
BigInt::BigInt(const int &x) {
sgn = (x >= 0 ? 1 : 0);
int r = abs(x);
while (r) {
dig.push_back(r % base);
r /= base;
}
}
BigInt::BigInt(const string &s) {
int pos = 0;
sgn = 1;
if (s[0] == '-') {
sgn = 0;
pos = 1;
}
for (int i = (int)s.size() - len; i >= pos; i -= len)
dig.push_back(stoi(s.substr(i, len)));
if (((int)s.size() - pos) % len != 0)
dig.push_back(stoi(s.substr(pos, ((int)s.size() - pos) % len)));
}
BigInt operator - (const BigInt &a) {
BigInt res = a;
res.sgn ^= 1;
return res;
}
void BigInt::normalize() {
for (int i = 0; i < dig.size(); ++i) {
if (dig[i] >= base) {
int r = dig[i] / base;
dig[i] %= base;
if (i + 1 == dig.size())
dig.push_back(0);
dig[i + 1] += r;
}
if (dig[i] < 0) {
dig[i] += base;
--dig[i + 1];
}
}
while (dig.size() > 1 && dig[dig.size() - 1] == 0)
dig.pop_back();
if (dig.size() == 1 && dig[0] == 0)
sgn = 1;
}
bool BigInt::operator > (const BigInt &a) const {
return !((*this) < a || (*this) == a);
}
bool BigInt::operator < (const BigInt &a) const {
if (!sgn && a.sgn)
return true;
else if (sgn && !a.sgn)
return false;
const bool change = (sgn == 0);
if (dig.size() < a.dig.size())
return true ^ change;
else if (dig.size() > a.dig.size())
return false ^ change;
else {
for (int i = (int)dig.size() - 1; i >= 0; --i) {
if (dig[i] < a.dig[i])
return true ^ change;
else if (dig[i] > a.dig[i])
return false ^ change;
}
}
return false;
}
bool BigInt::operator == (const BigInt &a) const {
if (sgn != a.sgn || dig.size() != a.dig.size())
return false;
for (int i = 0; i < dig.size(); ++i) {
if (dig[i] != a.dig[i])
return false;
}
return true;
}
istream & operator >> (istream &in, BigInt &a) {
string s;
in >> s;
a = BigInt(s);
return in;
}
ostream & operator << (ostream &out, const BigInt &a) {
if (a.dig.empty()) {
out << 0;
return out;
}
if (!a.sgn)
out << '-';
out << a.dig.back();
out.fill('0');
for (int i = (int)a.dig.size() - 2; i >= 0; --i) {
out << setw(a.len) << a.dig[i];
}
return out;
}
BigInt& BigInt::operator ++ (int) {
if (*this == BigInt(0)) {
*this = BigInt(1);
return *this;
}
if (sgn == 1) {
++dig[0];
normalize();
return *this;
}
else {
--dig[0];
normalize();
return *this;
}
}
BigInt BigInt::operator + (const BigInt &a) const {
if (a == BigInt(0))
return *this;
if (sgn == a.sgn) {
BigInt res = *this;
res.dig.resize(max(dig.size(), a.dig.size()) + 1);
for (int i = 0; i < a.dig.size(); ++i) {
res.dig[i] += a.dig[i];
}
res.normalize();
return res;
}
else {
return *this - (-a);
}
}
BigInt BigInt::operator - (const BigInt &a) const {
if (a == BigInt(0))
return *this;
if (*this == a)
return BigInt(0);
if (sgn == a.sgn) {
if (babs() < a.babs()) {
BigInt res = a - *this;
res.sgn = a.sgn ^ 1;
return res;
}
else {
BigInt res = *this;
res.sgn = sgn;
for (int i = 0; i < a.dig.size(); ++i) {
res.dig[i] -= a.dig[i];
}
res.normalize();
return res;
}
}
else {
return *this + (-a);
}
}
BigInt BigInt::operator * (const BigInt &a) const {
if (a == BigInt(0) || *this == BigInt(0))
return BigInt(0);
BigInt res;
res.sgn = !((!sgn) ^ (!a.sgn));
res.dig.resize(dig.size() + a.dig.size());
for (int i = 0; i < dig.size(); ++i) {
for (int j = 0; j < a.dig.size(); ++j) {
long long f = dig[i] * 1ll * a.dig[j] + res.dig[i + j];
res.dig[i + j] = f % base;
res.dig[i + j + 1] += f / base;
}
}
res.normalize();
return res;
}
BigInt BigInt::operator / (const int &x) const {
BigInt res;
res.sgn = sgn;
res.dig.resize(dig.size());
if (x < 0)
res.sgn ^= 1;
int X = abs(x), carry = 0;
for (int i = (int)dig.size() - 1; i >= 0; --i) {
long long cur = base * 1ll * carry + dig[i];
res.dig[i] = cur / X;
carry = cur % X;
}
res.normalize();
if (res.sgn == 0 && carry > 0)
res = res - BigInt(1);
return res;
}
int BigInt::operator % (const int &x) const {
bool Sgn = !((!sgn) ^ (x < 0));
int X = abs(x), carry = 0;
for (int i = dig.size() - 1; i >= 0; --i) {
long long cur = base * 1ll * carry + dig[i];
carry = cur % X;
}
if (Sgn == 0)
carry = (X - carry) % X;
return carry;
}
BigInt INF;
BigInt one;
inline BigInt gett(const BigInt &a) {
BigInt result = a * BigInt(2);
BigInt l(0), r = INF, mid, c;
while (r - l > one) {
mid = (l + r) / 2;
c = (mid * (mid + one)) / 2;
if (!(c > a)) l = mid;
else r = mid;
}
result = result - l;
return result;
}
inline void solve() {
string s(200, '9'); INF = BigInt(s);
one = BigInt(1);
BigInt n; cin >> n;
cout << BigInt(1) + gett(n - BigInt(1));
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int q = 1; // cin >> q;
while (q--) solve();
cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}
Compilation message
oddeven.cpp: In member function 'void BigInt::normalize()':
oddeven.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for (int i = 0; i < dig.size(); ++i) {
| ~~^~~~~~~~~~~~
oddeven.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | if (i + 1 == dig.size())
| ~~~~~~^~~~~~~~~~~~~
oddeven.cpp: In member function 'bool BigInt::operator==(const BigInt&) const':
oddeven.cpp:137:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for (int i = 0; i < dig.size(); ++i) {
| ~~^~~~~~~~~~~~
oddeven.cpp: In member function 'BigInt BigInt::operator+(const BigInt&) const':
oddeven.cpp:191:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
191 | for (int i = 0; i < a.dig.size(); ++i) {
| ~~^~~~~~~~~~~~~~
oddeven.cpp: In member function 'BigInt BigInt::operator-(const BigInt&) const':
oddeven.cpp:215:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
215 | for (int i = 0; i < a.dig.size(); ++i) {
| ~~^~~~~~~~~~~~~~
oddeven.cpp: In member function 'BigInt BigInt::operator*(const BigInt&) const':
oddeven.cpp:235:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
235 | for (int i = 0; i < dig.size(); ++i) {
| ~~^~~~~~~~~~~~
oddeven.cpp:236:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
236 | for (int j = 0; j < a.dig.size(); ++j) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
2 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
320 KB |
Output is correct |
| 6 |
Correct |
1 ms |
328 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
2 ms |
260 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
2 ms |
212 KB |
Output is correct |
| 13 |
Correct |
2 ms |
320 KB |
Output is correct |
| 14 |
Correct |
3 ms |
212 KB |
Output is correct |
| 15 |
Correct |
2 ms |
212 KB |
Output is correct |
| 16 |
Correct |
1 ms |
212 KB |
Output is correct |
| 17 |
Correct |
2 ms |
324 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
2 ms |
212 KB |
Output is correct |
| 20 |
Correct |
1 ms |
308 KB |
Output is correct |
| 21 |
Correct |
2 ms |
212 KB |
Output is correct |
| 22 |
Correct |
1 ms |
212 KB |
Output is correct |
