Submission #893118

#	Time	Username	Problem	Language	Result	Execution time	Memory
893118		presko	Odd-even (IZhO11_oddeven)	C++14	100 / 100	32 ms	464 KiB

oddeven

#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 (stderr)

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++)
      |                 ~^~~~~~~~~

• Subtask 1: 100 / 100