#ifndef Local
#pragma GCC optimize("O3,unroll-loops")
const int lim=200;
#else
const int lim=200;
#endif
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define pb push_back
const int mod=1e9+7;
using pii=pair<int,int>;
using longnum=bitset<4*lim>;
longnum powof10[lim+1];
//if a>b == 1
// a<b == -1
// a=b == 0
inline int comp(longnum a,longnum b){
for(int i=4*lim-1;0<=i;i--){
if(a[i]&&!b[i])return 1;
if(!a[i]&&b[i])return -1;
}
return 0;
}
inline longnum sum(longnum a,longnum b){
while(b.any()){
longnum x=a^b,y=a&b;
a=x,b=y<<1;
}
return a;
}
inline longnum sub(longnum a,longnum b){
b=sum(b.flip(),1);
return sum(a,b);
}
inline string tostring(longnum a){
if(!a.any())return "0";
string s;
if(a[4*lim-1]){
s.pb('-');
a=sub(0,a);
}
for(int i=lim-1;0<=i;i--){
int k=0;
while(~comp(a,powof10[i])){
a=sub(a,powof10[i]);
k++;
}
if((s.size()&&s.back()!='-')||k){
s.pb(k);
}
}
if(s[0]=='-')s[0]-='0';
for(int i=0;i<s.size();i++){
s[i]+='0';
}
return s;
}
inline longnum mul(longnum a,longnum b){
longnum res=0;
while(b.any()){
if(b[0]){
res=sum(res,a);
}
a<<=1;
b>>=1;
}
return res;
}
inline longnum parse(string s){
for(int i=0;i<s.size();i++)s[i]-='0';
longnum res=0,cur=1;
for(int i=s.size()-1;0<=i;i--){
res=sum(res,mul(cur,s[i]));
cur=mul(cur,10);
}
return res;
}
void solve(){
powof10[0]=1;
for(int i=1;i<=lim;i++){
powof10[i]=mul(powof10[i-1],10);
}
string s;
cin>>s;
longnum n=parse(s);
longnum l=1,r=powof10[50],ans=0;
while(~comp(r,l)){
longnum m=sum(l,r)>>1;
int res=comp(
mul(m,sum(m,1))>>1
,n);
if(!res){
ans=m;
//cerr<<tostring(m)<<" "<<tostring(sub(mul(sum(m,2),sum(m,1))>>1,1))<<" does\n";
break;
}
if(res==-1){
l=sum(m,1);
}else{
ans=m;
//cerr<<tostring(m)<<" "<<tostring(sub(mul(sum(m,2),sum(m,1))>>1,1))<<" does\n";
r=sub(m,1);
}
}
longnum prev=mul(sub(ans,1),sub(ans,1));
longnum pastcount=mul(ans,sub(ans,1))>>1;
longnum till=sub(n,pastcount);
cout<<tostring(
sub(sum(prev,till<<1),1)
)<<"\n";
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
#ifdef Local
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#else
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
#endif
int t=1;
//cin>>t;
while (t--)
{
solve();
}
}
Compilation message
oddeven.cpp: In function 'std::string tostring(longnum)':
oddeven.cpp:63:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0;i<s.size();i++){
| ~^~~~~~~~~
oddeven.cpp: In function 'longnum parse(std::string)':
oddeven.cpp:80:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i=0;i<s.size();i++)s[i]-='0';
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
468 KB |
Output is correct |
| 3 |
Correct |
3 ms |
348 KB |
Output is correct |
| 4 |
Correct |
3 ms |
348 KB |
Output is correct |
| 5 |
Correct |
3 ms |
472 KB |
Output is correct |
| 6 |
Correct |
3 ms |
484 KB |
Output is correct |
| 7 |
Correct |
3 ms |
348 KB |
Output is correct |
| 8 |
Correct |
3 ms |
476 KB |
Output is correct |
| 9 |
Correct |
3 ms |
348 KB |
Output is correct |
| 10 |
Correct |
3 ms |
348 KB |
Output is correct |
| 11 |
Correct |
3 ms |
348 KB |
Output is correct |
| 12 |
Correct |
3 ms |
348 KB |
Output is correct |
| 13 |
Correct |
4 ms |
476 KB |
Output is correct |
| 14 |
Correct |
4 ms |
344 KB |
Output is correct |
| 15 |
Correct |
4 ms |
348 KB |
Output is correct |
| 16 |
Correct |
4 ms |
348 KB |
Output is correct |
| 17 |
Correct |
5 ms |
348 KB |
Output is correct |
| 18 |
Correct |
6 ms |
476 KB |
Output is correct |
| 19 |
Correct |
6 ms |
348 KB |
Output is correct |
| 20 |
Correct |
7 ms |
348 KB |
Output is correct |
| 21 |
Correct |
6 ms |
348 KB |
Output is correct |
| 22 |
Correct |
6 ms |
348 KB |
Output is correct |
