Submission #89374

#	Time	Username	Problem	Language	Result	Execution time	Memory
89374		vex	Poklon (COCI17_poklon7)	C++14	42 / 120	331 ms	40736 KiB

poklon

#include <bits/stdc++.h>
#define maxn 1000005
#define pll_i pair<long long,int>
#define broj first
#define ste2 second
using namespace std;

int n;
int l[maxn];
int r[maxn];

pll_i veci(pll_i a,pll_i b)
{
    if(a.ste2<b.ste2)
    {
        swap(a.broj,b.broj);
        swap(a.ste2,b.ste2);
    }

    a.ste2-=b.ste2;

    long long kol=b.broj/a.broj;

    int br2=0;
    while(kol>=2)
    {
        br2++;
        kol/=2;
    }

    if(br2>=a.ste2)return b;
    else
    {
        a.ste2+=b.ste2;
        return a;
    }
}

pll_i resi(int x)
{
    pll_i res1,res2;
    if(l[x]>0)res1=resi(l[x]);else res1={-l[x],0};
    if(r[x]>0)res2=resi(r[x]);else res2={-r[x],0};

    pll_i sol=veci(res1,res2);
    sol.ste2++;

    //cout<<res1.broj<<","<<res1.ste2<<" "<<res2.broj<<","<<res2.ste2<<" "<<sol.broj<<","<<sol.ste2<<endl;

    return sol;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>l[i]>>r[i];
    }

    pll_i sol=resi(1);

    //cout<<sol.broj<<" "<<sol.ste2<<endl;

    string s;
    while(sol.broj>0)
    {
        s.push_back(sol.broj%2 + '0');
        sol.broj/=2;
    }
    int len=s.size();
    for(int i=len-1;i>=0;i--)cout<<s[i];
    while(sol.ste2>0)
    {
        cout<<"0";
        sol.ste2--;
    }

    /*string s;
    while(sol>0)
    {
        s.push_back(sol%2 + '0');
        sol/=2;
    }

    int len=s.size();
    for(int i=len-1;i>=0;i--)cout<<s[i];*/
    return 0;
}

• Subtask 1: 42 / 120