Submission #882058

#	Time	Username	Problem	Language	Result	Execution time	Memory
882058		noyancanturk	Odd-even (IZhO11_oddeven)	C++17	100 / 100	7 ms	600 KiB

oddeven

#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;
            break;
        }
        if(res==-1){
            l=sum(m,1);
        }else{
            ans=m;
            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 (stderr)

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';
      |                 ~^~~~~~~~~

• Subtask 1: 100 / 100