Submission #881056

#	Time	Username	Problem	Language	Result	Execution time	Memory
881056		alexdd	Odd-even (IZhO11_oddeven)	C++17	100 / 100	27 ms	604 KiB

oddeven

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
#define int long long
struct big_int
{
    int nrcif;
    int cif[205];
};
big_int emp = {0,{}};
big_int unu = {1,{-1,1}};
big_int aduna(big_int a, big_int b)
{
    if(a.nrcif==0)
        return b;
    if(b.nrcif==0)
        return a;
    big_int rez;
    rez.nrcif=0;
    int r=0;
    for(int i=1;i<=max(a.nrcif,b.nrcif);i++)
    {
        if(i<=a.nrcif) r += a.cif[i];
        if(i<=b.nrcif) r += b.cif[i];
        rez.cif[i] = r%10;
        rez.nrcif = i;
        r/=10;
    }
    while(r>0)
    {
        rez.cif[++rez.nrcif] = r%10;
        r/=10;
    }
    return rez;
}
big_int scadere(big_int a, big_int b)
{
    for(int i=1;i<=a.nrcif;i++)
    {
        int cifb;
        if(i<=b.nrcif)
            cifb=b.cif[i];
        else
            cifb=0;
        if(a.cif[i]>=cifb)
            a.cif[i] -= cifb;
        else
        {
            int j=i+1;
            while(a.cif[j]==0)
                a.cif[j++]=9;
            a.cif[j]--;
            a.cif[i] = 10 + a.cif[i] - cifb;
        }
    }
    while(a.cif[a.nrcif]==0)
        a.nrcif--;
    return a;
}
big_int inm_nrmic(big_int a, int x)
{
    if(a.nrcif==0 || x==0)
        return emp;
    int r=0;
    for(int i=1;i<=a.nrcif;i++)
    {
        r += a.cif[i] * x;
        a.cif[i] = r%10;
        r/=10;
    }
    while(r>0)
    {
        a.cif[++a.nrcif] = r%10;
        r/=10;
    }
    return a;
}
big_int inm10(big_int a, int p10)
{
    big_int rez;
    rez.nrcif = p10 + a.nrcif;
    for(int i=1;i<=p10;i++)
        rez.cif[i] = 0;
    for(int i=1;i<=a.nrcif;i++)
        rez.cif[p10+i] = a.cif[i];
    return rez;
}
big_int inm_nrmari(big_int a, big_int b)
{
    if(a.nrcif==0 || b.nrcif==0)
        return emp;
    big_int rez = emp;
    for(int i=1;i<=b.nrcif;i++)
    {
        rez = aduna(rez, inm10(inm_nrmic(a,b.cif[i]), i-1));
    }
    return rez;
}
bool compara(big_int a, big_int b)///return 1   daca a<=b
{
    if(a.nrcif < b.nrcif)
        return 1;
    if(a.nrcif > b.nrcif)
        return 0;
    for(int i=a.nrcif;i>0;i--)
    {
        if(a.cif[i] < b.cif[i])
            return 1;
        if(a.cif[i] > b.cif[i])
            return 0;
    }
    return 1;
}
void afis(big_int a)
{
    for(int i=a.nrcif;i>0;i--)
        cout<<a.cif[i];
    cout<<"\n";
}
big_int citeste()
{
    string s;
    cin>>s;
    big_int rez;
    rez.nrcif = 0;
    for(int i = (int)s.size()-1;i>=0;i--)
        rez.cif[++rez.nrcif] = s[i]-'0';
    return rez;
}
void solve_mici(int n)
{
    int nrs=sqrt(2LL*(n-1));
    nrs = max(0LL, nrs-5);
    for(int i=nrs;i<=2e9;i++)
    {
        if(i*(i+1)<=2LL*(n-1))
        {
            nrs=i;
        }
        else
            break;
    }
    //cout<<n<<" "<<1LL + (n-1)*2LL - nrs<<"\n";
    cout<<n*2LL - nrs - 1<<"\n";
    //cout<<n<<" "<<nrs<<"\n";
}
signed main()
{
    //solve_mici(129834123);return 0;
    /*big_int a = {5,{-1,1,9,3,4,5}};
    big_int b = {3,{-1,8,7,6}};
    afis(a);
    afis(b);
    cout<<"a+b = ";afis(aduna(a,b));
    cout<<"a*b = ";afis(inm_nrmari(a,b));*/
    big_int n = citeste();
    //afis(inm_nrmic(scadere(n,unu),2));
    //return 0;
    big_int nrs = emp;
    for(int i=100;i>=0;i--)
    {
        for(int j=9;j>0;j--)
        {
            big_int news = aduna(nrs,inm10({1,{-1,j}},i));
            //continue;
            if(compara(inm_nrmari(news,aduna(news,unu)), inm_nrmic(scadere(n,unu),2)))
            {
                nrs = news;
                break;
            }
        }
    }
    //afis(nrs);
    //afis(inm_nrmic(n,2));
    //afis(aduna(nrs,unu));
    afis(scadere(inm_nrmic(n,2),aduna(nrs,unu)));
    return 0;
}
/**

nrs * (nrs+1) / 2 <= n

*/

• Subtask 1: 100 / 100