#include<iostream>
#include<bits/stdc++.h>
using namespace std;
string add(string res, string curr)
{
string ret="";
int lastres=res.size()-1,lastcurr=curr.size()-1,carry=0;
while(lastres>-1 && lastcurr>-1)
{
int digres = res[lastres]-'0';
int digcurr = curr[lastcurr]-'0';
ret+=(digres+digcurr+carry)%10+'0';
carry=(digres+digcurr+carry)/10;
lastres--;
lastcurr--;
}
if(lastres>-1)
{
while(lastres>-1)
{
int digres = res[lastres]-'0';
ret+=(digres+carry)%10+'0';
carry=(digres+carry)/10;
lastres--;
}
}
else if(lastcurr>-1)
{
while(lastcurr>-1)
{
int digcurr = curr[lastcurr]-'0';
ret+=(digcurr+carry)%10+'0';
carry=(digcurr+carry)/10;
lastcurr--;
}
}
if(carry>0)ret+=(carry+'0');
reverse(ret.begin(),ret.end());
return ret;
}
string mult(string a, string n)
{
string res="";
for(int i=n.size()-1;i>=0;i--)
{
string curr="";
int z=n.size()-i-1;
while(z>0)
{
curr+='0';
z--;
}
short dign = n[i]-'0',cry=0;
for(int j=a.size()-1;j>=0;j--)
{
short diga = a[j]-'0';
curr+=(((diga*dign)+cry)%10+'0');
cry=((diga*dign)+cry)/10;
}
if(cry>0)curr+=cry+'0';
reverse(curr.begin(),curr.end());
res=add(res,curr);
}
return res;
}
string div(string s)
{
if(s=="0")return "0";//important
int st=0;
string res="";
bool fl=0;
if(s[0]=='1')
{
if(s.size()==1)return "0";
fl=1;
st=1;
}
for(int i=st;i<s.size();i++)
{
int dig=s[i]-'0',val=dig;
if(fl)val+=10;
if((val&1)==0)fl=0;
else fl=1;
char d = (val>>1)+'0';
res=res+d;
}
return res;
}
string subtr(string n, string q)
{
string ret="";
int lastn=n.size()-1,lastq=q.size()-1,carry=0;
while(lastq>-1)
{
int dign = n[lastn]-'0';
int digq = q[lastq]-'0';
if(dign-digq-carry>=0){ret+=(dign-digq-carry)%10+'0';carry=0;}
else {ret+=(dign-digq-carry+10)%10+'0';carry=1;}
lastn--;
lastq--;
}
if(lastn>-1)
{
while(lastn>-1)
{
int dign = n[lastn]-'0';
if(dign-carry>=0){ret+=(dign-carry)%10+'0';carry=0;}
else {ret+=(dign-carry+10)%10+'0';carry=1;}
lastn--;
}
}
reverse(ret.begin(),ret.end());
lastn=0;
for(int i=0;i<ret.size();i++)
{
if(ret[i]=='0')lastn++;
else break;
}
ret=ret.substr(lastn,ret.size());
if(ret=="")return "0";
return ret;
}
int cmp(string x, string y)
{
if(x.size()<y.size())return -1;
else if(x.size()>y.size())return 1;
for(int i=0;i<x.size();i++)
{
if(x[i]!=y[i])
{
if(x[i]>y[i])return 1;
else return -1;
}
}
return 0;
}
string getseg(string s)
{
string l="1",r=s,ans="a";
while(cmp(r,add(l,"1"))==1)
{
string mid=div(add(l,r));
string st,en;
en=div(mult(mid,add(mid,"1")));
st=subtr(en,subtr(mid,"1"));
if(cmp(s,st)==-1)r=mid;
else if(cmp(s,en)==1)l=mid;
else {ans=mid;break;}
}
if(ans!="a")return ans;
string bl,br;
br=div(mult(l,add(l,"1")));
bl=subtr(br,subtr(l,"1"));
if(bl<=s && s<=br)return l;
else return r;
}
int main()
{
string s;
ios_base::sync_with_stdio(false);
cin.tie(0);
cin>>s;
string seg=getseg(s);
string fin=mult(seg,seg);
string en=div(mult(seg,add(seg,"1")));
string diff=mult(subtr(en,s),"2");
string ans=subtr(fin,diff);
cout<<ans<<"\n";
}
Compilation message
oddeven.cpp: In function 'std::string div(std::string)':
oddeven.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i=st;i<s.size();i++)
| ~^~~~~~~~~
oddeven.cpp: In function 'std::string subtr(std::string, std::string)':
oddeven.cpp:114:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | for(int i=0;i<ret.size();i++)
| ~^~~~~~~~~~~
oddeven.cpp: In function 'int cmp(std::string, std::string)':
oddeven.cpp:128:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for(int i=0;i<x.size();i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
0 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
344 KB |
Output is correct |
| 10 |
Correct |
0 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
2 ms |
348 KB |
Output is correct |
| 14 |
Correct |
3 ms |
348 KB |
Output is correct |
| 15 |
Correct |
6 ms |
456 KB |
Output is correct |
| 16 |
Correct |
7 ms |
348 KB |
Output is correct |
| 17 |
Correct |
12 ms |
348 KB |
Output is correct |
| 18 |
Correct |
21 ms |
464 KB |
Output is correct |
| 19 |
Correct |
25 ms |
348 KB |
Output is correct |
| 20 |
Correct |
26 ms |
348 KB |
Output is correct |
| 21 |
Correct |
25 ms |
348 KB |
Output is correct |
| 22 |
Correct |
32 ms |
348 KB |
Output is correct |
