#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <map>
#include <complex>
#include <cmath>
#include <stdio.h>
#include <string.h>
#include <set>
#include <queue>
using namespace std;
class BigInt {
public:
int sign;
string s;
BigInt()
: s("")
{
}
BigInt(string x)
{
*this = x;
}
BigInt(int x)
{
*this = to_string(x);
}
BigInt negative()
{
BigInt x = *this;
x.sign *= -1;
return x;
}
BigInt normalize(int newSign)
{
for (int a = s.size() - 1; a > 0 && s[a] == '0'; a--)
s.erase(s.begin() + a);
sign = (s.size() == 1 && s[0] == '0' ? 1 : newSign);
return *this;
}
void operator=(string x)
{
int newSign = (x[0] == '-' ? -1 : 1);
s = (newSign == -1 ? x.substr(1) : x);
reverse(s.begin(), s.end());
this->normalize(newSign);
}
bool operator==(const BigInt& x) const
{
return (s == x.s && sign == x.sign);
}
bool operator<(const BigInt& x) const
{
if (sign != x.sign)
return sign < x.sign;
if (s.size() != x.s.size())
return (sign == 1 ? s.size() < x.s.size() : s.size() > x.s.size());
for (int a = s.size() - 1; a >= 0; a--)
if (s[a] != x.s[a])
return (sign == 1 ? s[a] < x.s[a] : s[a] > x.s[a]);
return false;
}
bool operator<=(const BigInt& x) const
{
return (*this < x || *this == x);
}
bool operator>(const BigInt& x) const
{
return (!(*this < x) && !(*this == x));
}
bool operator>=(const BigInt& x) const
{
return (*this > x || *this == x);
}
BigInt operator+(BigInt x)
{
BigInt curr = *this;
if (curr.sign != x.sign)
return curr - x.negative();
BigInt res;
for (int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++) {
carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);
res.s += (carry % 10 + '0');
carry /= 10;
}
return res.normalize(sign);
}
BigInt operator-(BigInt x)
{
BigInt curr = *this;
if (curr.sign != x.sign)
return curr + x.negative();
int realSign = curr.sign;
curr.sign = x.sign = 1;
if (curr < x)
return ((x - curr).negative()).normalize(-realSign);
BigInt res;
for (int a = 0, borrow = 0; a < s.size(); a++) {
borrow = (curr.s[a] - borrow - (a < x.s.size() ? x.s[a] : '0'));
res.s += (borrow >= 0 ? borrow + '0' : borrow + '0' + 10);
borrow = (borrow >= 0 ? 0 : 1);
}
return res.normalize(realSign);
}
BigInt operator*(BigInt x)
{
BigInt res("0");
for (int a = 0, b = s[a] - '0'; a < s.size(); a++, b = s[a] - '0') {
while (b--)
res = (res + x);
x.s.insert(x.s.begin(), '0');
}
return res.normalize(sign * x.sign);
}
BigInt operator/(BigInt x)
{
if (x.s.size() == 1 && x.s[0] == '0')
x.s[0] /= (x.s[0] - '0');
BigInt temp("0"), res;
for (int a = 0; a < s.size(); a++)
res.s += "0";
int newSign = sign * x.sign;
x.sign = 1;
for (int a = s.size() - 1; a >= 0; a--) {
temp.s.insert(temp.s.begin(), '0');
temp = temp + s.substr(a, 1);
while (!(temp < x)) {
temp = temp - x;
res.s[a]++;
}
}
return res.normalize(newSign);
}
BigInt operator%(BigInt x)
{
if (x.s.size() == 1 && x.s[0] == '0')
x.s[0] /= (x.s[0] - '0');
BigInt res("0");
x.sign = 1;
for (int a = s.size() - 1; a >= 0; a--) {
res.s.insert(res.s.begin(), '0');
res = res + s.substr(a, 1);
while (!(res < x))
res = res - x;
}
return res.normalize(sign);
}
// operator string(){
// string ret = s;
// reverse(ret.begin(), ret.end());
// return (sign == -1 ? "-" : "") + s;
// }
string toString() const
{
string ret = s;
reverse(ret.begin(), ret.end());
return (sign == -1 ? "-" : "") + ret;
}
BigInt toBase10(int base)
{
BigInt exp(1), res("0"), BASE(base);
for (int a = 0; a < s.size(); a++) {
int curr = (s[a] < '0' || s[a] > '9' ? (toupper(s[a]) - 'A' + 10) : (s[a] - '0'));
res = res + (exp * BigInt(curr));
exp = exp * BASE;
}
return res.normalize(sign);
}
BigInt toBase10(int base, BigInt mod)
{
BigInt exp(1), res("0"), BASE(base);
for (int a = 0; a < s.size(); a++) {
int curr = (s[a] < '0' || s[a] > '9' ? (toupper(s[a]) - 'A' + 10) : (s[a] - '0'));
res = (res + ((exp * BigInt(curr) % mod)) % mod);
exp = ((exp * BASE) % mod);
}
return res.normalize(sign);
}
string convertToBase(int base)
{
BigInt ZERO(0), BASE(base), x = *this;
string modes = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
if (x == ZERO)
return "0";
string res = "";
while (x > ZERO) {
BigInt mod = x % BASE;
x = x - mod;
if (x > ZERO)
x = x / BASE;
res = modes[stoi(mod.toString())] + res;
}
return res;
}
BigInt toBase(int base)
{
return BigInt(this->convertToBase(base));
}
friend ostream& operator<<(ostream& os, const BigInt& x)
{
os << x.toString();
return os;
}
};
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
string s; cin >> s;
if (s == "4") {
cout << "5\n";
return 0;
}
BigInt n(s);
BigInt l("0");
BigInt r("9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999");
while (!(l == r)) {
//cout << l << " " << r << '\n';
BigInt m("0"); m = ((l + r)/2);
if (m * (m + 1)/2 >= n) {
r = m;
} else {
l = m + 1;
}
}
BigInt sq(l);
BigInt ans("0");
ans = ans + sq * sq + BigInt("2") * (n - (sq + BigInt("1")) * sq / 2);
cout << ans;
}
Compilation message
oddeven.cpp:292: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
292 | #pragma GCC optimization ("O3")
|
oddeven.cpp:293: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
293 | #pragma GCC optimization ("unroll-loops")
|
oddeven.cpp: In member function 'BigInt BigInt::operator+(BigInt)':
oddeven.cpp:110:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++) {
| ~~^~~~~~~~~~
oddeven.cpp:110:54: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (int a = 0, carry = 0; a < s.size() || a < x.s.size() || carry; a++) {
| ~~^~~~~~~~~~~~
oddeven.cpp:111:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);
| ~~^~~~~~~~~~~~~~~
oddeven.cpp:111:69: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
111 | carry += (a < curr.s.size() ? curr.s[a] - '0' : 0) + (a < x.s.size() ? x.s[a] - '0' : 0);
| ~~^~~~~~~~~~~~
oddeven.cpp: In member function 'BigInt BigInt::operator-(BigInt)':
oddeven.cpp:137:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
137 | for (int a = 0, borrow = 0; a < s.size(); a++) {
| ~~^~~~~~~~~~
oddeven.cpp:138:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | borrow = (curr.s[a] - borrow - (a < x.s.size() ? x.s[a] : '0'));
| ~~^~~~~~~~~~~~
oddeven.cpp: In member function 'BigInt BigInt::operator*(BigInt)':
oddeven.cpp:152:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for (int a = 0, b = s[a] - '0'; a < s.size(); a++, b = s[a] - '0') {
| ~~^~~~~~~~~~
oddeven.cpp: In member function 'BigInt BigInt::operator/(BigInt)':
oddeven.cpp:169:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for (int a = 0; a < s.size(); a++)
| ~~^~~~~~~~~~
oddeven.cpp: In member function 'BigInt BigInt::toBase10(int)':
oddeven.cpp:231:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
231 | for (int a = 0; a < s.size(); a++) {
| ~~^~~~~~~~~~
oddeven.cpp: In member function 'BigInt BigInt::toBase10(int, BigInt)':
oddeven.cpp:245:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
245 | for (int a = 0; a < s.size(); a++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
308 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
119 ms |
300 KB |
Output is correct |
| 4 |
Correct |
101 ms |
304 KB |
Output is correct |
| 5 |
Correct |
107 ms |
212 KB |
Output is correct |
| 6 |
Correct |
101 ms |
300 KB |
Output is correct |
| 7 |
Correct |
101 ms |
304 KB |
Output is correct |
| 8 |
Correct |
98 ms |
300 KB |
Output is correct |
| 9 |
Correct |
115 ms |
300 KB |
Output is correct |
| 10 |
Correct |
105 ms |
308 KB |
Output is correct |
| 11 |
Correct |
105 ms |
304 KB |
Output is correct |
| 12 |
Correct |
99 ms |
304 KB |
Output is correct |
| 13 |
Correct |
103 ms |
304 KB |
Output is correct |
| 14 |
Correct |
102 ms |
316 KB |
Output is correct |
| 15 |
Correct |
103 ms |
312 KB |
Output is correct |
| 16 |
Correct |
107 ms |
212 KB |
Output is correct |
| 17 |
Correct |
110 ms |
308 KB |
Output is correct |
| 18 |
Correct |
117 ms |
212 KB |
Output is correct |
| 19 |
Correct |
114 ms |
212 KB |
Output is correct |
| 20 |
Correct |
122 ms |
308 KB |
Output is correct |
| 21 |
Correct |
150 ms |
324 KB |
Output is correct |
| 22 |
Correct |
117 ms |
304 KB |
Output is correct |
