#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{
string digits;
public:
//Constructors:
BigInt(unsigned long long n = 0);
BigInt(string &);
BigInt(const char *);
BigInt(BigInt &);
//Helper Functions:
friend void divide_by_2(BigInt &a);
friend bool Null(const BigInt &);
friend int Length(const BigInt &);
int operator[](const int)const;
/* * * * Operator Overloading * * * */
//Direct assignment
BigInt &operator=(const BigInt &);
//Post/Pre - Incrementation
BigInt &operator++();
BigInt operator++(int temp);
BigInt &operator--();
BigInt operator--(int temp);
//Addition and Subtraction
friend BigInt &operator+=(BigInt &, const BigInt &);
friend BigInt operator+(const BigInt &, const BigInt &);
friend BigInt operator-(const BigInt &, const BigInt &);
friend BigInt &operator-=(BigInt &, const BigInt &);
//Comparison operators
friend bool operator==(const BigInt &, const BigInt &);
friend bool operator!=(const BigInt &, const BigInt &);
friend bool operator>(const BigInt &, const BigInt &);
friend bool operator>=(const BigInt &, const BigInt &);
friend bool operator<(const BigInt &, const BigInt &);
friend bool operator<=(const BigInt &, const BigInt &);
//Multiplication and Division
friend BigInt &operator*=(BigInt &, const BigInt &);
friend BigInt operator*(const BigInt &, const BigInt &);
friend BigInt &operator/=(BigInt &, const BigInt &);
friend BigInt operator/(const BigInt &, const BigInt &);
//Modulo
friend BigInt operator%(const BigInt &, const BigInt &);
friend BigInt &operator%=(BigInt &, const BigInt &);
//Power Function
friend BigInt &operator^=(BigInt &,const BigInt &);
friend BigInt operator^(BigInt &, const BigInt &);
//Square Root Function
friend BigInt sqrt(BigInt &a);
//Read and Write
friend ostream &operator<<(ostream &,const BigInt &);
friend istream &operator>>(istream &, BigInt &);
//Others
friend BigInt NthCatalan(int n);
friend BigInt NthFibonacci(int n);
friend BigInt Factorial(int n);
};
BigInt::BigInt(string & s){
digits = "";
int n = s.size();
for (int i = n - 1; i >= 0;i--){
if(!isdigit(s[i]))
throw("ERROR");
digits.push_back(s[i] - '0');
}
}
BigInt::BigInt(unsigned long long nr){
do{
digits.push_back(nr % 10);
nr /= 10;
} while (nr);
}
BigInt::BigInt(const char *s){
digits = "";
for (int i = strlen(s) - 1; i >= 0;i--)
{
if(!isdigit(s[i]))
throw("ERROR");
digits.push_back(s[i] - '0');
}
}
BigInt::BigInt(BigInt & a){
digits = a.digits;
}
bool Null(const BigInt& a){
if(a.digits.size() == 1 && a.digits[0] == 0)
return true;
return false;
}
int Length(const BigInt & a){
return a.digits.size();
}
int BigInt::operator[](const int index)const{
if(digits.size() <= index || index < 0)
throw("ERROR");
return digits[index];
}
bool operator==(const BigInt &a, const BigInt &b){
return a.digits == b.digits;
}
bool operator!=(const BigInt & a,const BigInt &b){
return !(a == b);
}
bool operator<(const BigInt&a,const BigInt&b){
int n = Length(a), m = Length(b);
if(n != m)
return n < m;
while(n--)
if(a.digits[n] != b.digits[n])
return a.digits[n] < b.digits[n];
return false;
}
bool operator>(const BigInt&a,const BigInt&b){
return b < a;
}
bool operator>=(const BigInt&a,const BigInt&b){
return !(a < b);
}
bool operator<=(const BigInt&a,const BigInt&b){
return !(a > b);
}
BigInt &BigInt::operator=(const BigInt &a){
digits = a.digits;
return *this;
}
BigInt &BigInt::operator++(){
int i, n = digits.size();
for (i = 0; i < n && digits[i] == 9;i++)
digits[i] = 0;
if(i == n)
digits.push_back(1);
else
digits[i]++;
return *this;
}
BigInt BigInt::operator++(int temp){
BigInt aux;
aux = *this;
++(*this);
return aux;
}
BigInt &BigInt::operator--(){
if(digits[0] == 0 && digits.size() == 1)
throw("UNDERFLOW");
int i, n = digits.size();
for (i = 0; digits[i] == 0 && i < n;i++)
digits[i] = 9;
digits[i]--;
if(n > 1 && digits[n - 1] == 0)
digits.pop_back();
return *this;
}
BigInt BigInt::operator--(int temp){
BigInt aux;
aux = *this;
--(*this);
return aux;
}
BigInt &operator+=(BigInt &a,const BigInt& b){
int t = 0, s, i;
int n = Length(a), m = Length(b);
if(m > n)
a.digits.append(m - n, 0);
n = Length(a);
for (i = 0; i < n;i++){
if(i < m)
s = (a.digits[i] + b.digits[i]) + t;
else
s = a.digits[i] + t;
t = s / 10;
a.digits[i] = (s % 10);
}
if(t)
a.digits.push_back(t);
return a;
}
BigInt operator+(const BigInt &a, const BigInt &b){
BigInt temp;
temp = a;
temp += b;
return temp;
}
BigInt &operator-=(BigInt&a,const BigInt &b){
if(a < b)
throw("UNDERFLOW");
int n = Length(a), m = Length(b);
int i, t = 0, s;
for (i = 0; i < n;i++){
if(i < m)
s = a.digits[i] - b.digits[i]+ t;
else
s = a.digits[i]+ t;
if(s < 0)
s += 10,
t = -1;
else
t = 0;
a.digits[i] = s;
}
while(n > 1 && a.digits[n - 1] == 0)
a.digits.pop_back(),
n--;
return a;
}
BigInt operator-(const BigInt& a,const BigInt&b){
BigInt temp;
temp = a;
temp -= b;
return temp;
}
BigInt &operator*=(BigInt &a, const BigInt &b)
{
if(Null(a) || Null(b)){
a = BigInt();
return a;
}
int n = a.digits.size(), m = b.digits.size();
vector<int> v(n + m, 0);
for (int i = 0; i < n;i++)
for (int j = 0; j < m;j++){
v[i + j] += (a.digits[i] ) * (b.digits[j]);
}
n += m;
a.digits.resize(v.size());
for (int s, i = 0, t = 0; i < n; i++)
{
s = t + v[i];
v[i] = s % 10;
t = s / 10;
a.digits[i] = v[i] ;
}
for (int i = n - 1; i >= 1 && !v[i];i--)
a.digits.pop_back();
return a;
}
BigInt operator*(const BigInt&a,const BigInt&b){
BigInt temp;
temp = a;
temp *= b;
return temp;
}
BigInt &operator/=(BigInt& a,const BigInt &b){
if(Null(b))
throw("Arithmetic Error: Division By 0");
if(a < b){
a = BigInt();
return a;
}
if(a == b){
a = BigInt(1);
return a;
}
int i, lgcat = 0, cc;
int n = Length(a), m = Length(b);
vector<int> cat(n, 0);
BigInt t;
for (i = n - 1; t * 10 + a.digits[i] < b;i--){
t *= 10;
t += a.digits[i] ;
}
for (; i >= 0; i--){
t = t * 10 + a.digits[i];
for (cc = 9; cc * b > t;cc--);
t -= cc * b;
cat[lgcat++] = cc;
}
a.digits.resize(cat.size());
for (i = 0; i < lgcat;i++)
a.digits[i] = cat[lgcat - i - 1];
a.digits.resize(lgcat);
return a;
}
BigInt operator/(const BigInt &a,const BigInt &b){
BigInt temp;
temp = a;
temp /= b;
return temp;
}
BigInt &operator%=(BigInt& a,const BigInt &b){
if(Null(b))
throw("Arithmetic Error: Division By 0");
if(a < b){
a = BigInt();
return a;
}
if(a == b){
a = BigInt(1);
return a;
}
int i, lgcat = 0, cc;
int n = Length(a), m = Length(b);
vector<int> cat(n, 0);
BigInt t;
for (i = n - 1; t * 10 + a.digits[i] < b;i--){
t *= 10;
t += a.digits[i];
}
for (; i >= 0; i--){
t = t * 10 + a.digits[i];
for (cc = 9; cc * b > t;cc--);
t -= cc * b;
cat[lgcat++] = cc;
}
a = t;
return a;
}
BigInt operator%(const BigInt &a,BigInt &b){
BigInt temp;
temp = a;
temp %= b;
return temp;
}
BigInt &operator^=(BigInt & a,const BigInt & b){
BigInt Exponent, Base(a);
Exponent = b;
a = 1;
while(!Null(Exponent)){
if(Exponent[0] & 1)
a *= Base;
Base *= Base;
divide_by_2(Exponent);
}
return a;
}
BigInt operator^(BigInt & a,BigInt & b){
BigInt temp(a);
temp ^= b;
return temp;
}
void divide_by_2(BigInt & a){
int add = 0;
for (int i = a.digits.size() - 1; i >= 0;i--){
int digit = (a.digits[i] >> 1) + add;
add = ((a.digits[i] & 1) * 5);
a.digits[i] = digit;
}
while(a.digits.size() > 1 && !a.digits.back())
a.digits.pop_back();
}
BigInt sqrt(BigInt & a){
BigInt left(1), right(a), v(1), mid, prod;
divide_by_2(right);
while(left <= right){
mid += left;
mid += right;
divide_by_2(mid);
prod = (mid * mid);
if(prod <= a){
v = mid;
++mid;
left = mid;
}
else{
--mid;
right = mid;
}
mid = BigInt();
}
return v;
}
BigInt NthCatalan(int n){
BigInt a(1),b;
for (int i = 2; i <= n;i++)
a *= i;
b = a;
for (int i = n + 1; i <= 2 * n;i++)
b *= i;
a *= a;
a *= (n + 1);
b /= a;
return b;
}
BigInt NthFibonacci(int n){
BigInt a(1), b(1), c;
if(!n)
return c;
n--;
while(n--){
c = a + b;
b = a;
a = c;
}
return b;
}
BigInt Factorial(int n){
BigInt f(1);
for (int i = 2; i <= n;i++)
f *= i;
return f;
}
istream &operator>>(istream &in,BigInt&a){
string s;
in >> s;
int n = s.size();
for (int i = n - 1; i >= 0;i--){
if(!isdigit(s[i]))
throw("INVALID NUMBER");
a.digits[n - i - 1] = s[i];
}
return in;
}
ostream &operator<<(ostream &out,const BigInt &a){
for (int i = a.digits.size() - 1; i >= 0;i--)
cout << (short)a.digits[i];
return cout;
}
#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 + (BigInt)("1"))/2);
if (m * (m + 1)/2 <= n) {
l = m;
} else {
r = m - 1;
}
}
BigInt sq(l);
BigInt ans("0");
ans += sq * sq;
ans += 2 * (n - (sq + BigInt("1")) * sq / 2);
cout << ans;
}
Compilation message
oddeven.cpp:452: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
452 | #pragma GCC optimization ("O3")
|
oddeven.cpp:453: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
453 | #pragma GCC optimization ("unroll-loops")
|
oddeven.cpp: In member function 'int BigInt::operator[](int) const':
oddeven.cpp:122:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
122 | if(digits.size() <= index || index < 0)
| ~~~~~~~~~~~~~~^~~~~~~~
oddeven.cpp: In function 'BigInt& operator/=(BigInt&, const BigInt&)':
oddeven.cpp:289:24: warning: unused variable 'm' [-Wunused-variable]
289 | int n = Length(a), m = Length(b);
| ^
oddeven.cpp: In function 'BigInt& operator%=(BigInt&, const BigInt&)':
oddeven.cpp:327:24: warning: unused variable 'm' [-Wunused-variable]
327 | int n = Length(a), m = Length(b);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
36 ms |
344 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
