Submission #89375

#	Time	Username	Problem	Language	Result	Execution time	Memory
89375		vex	Poklon (COCI17_poklon7)	C++14	120 / 120	385 ms	56464 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.broj<b.broj)
    {
        swap(a.broj,b.broj);
        swap(a.ste2,b.ste2);
    }

    int lg2_a=0,lg2_b=0;
    long long abr=a.broj;
    long long bbr=b.broj;

    while(abr>0LL)
    {
        lg2_a++;
        abr/=2;
    }

    while(bbr>0LL)
    {
        lg2_b++;
        bbr/=2;
    }
    bbr=b.broj;

    int ste2_b=b.ste2;
    while(lg2_b<lg2_a)
    {
        lg2_b++;
        bbr*=2;
        ste2_b--;
    }

    if(ste2_b>a.ste2)return b;
    if(ste2_b<a.ste2)return a;
    if(bbr>a.broj)return b;
    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: 120 / 120