oj.uz

Submission #89375

# Submission time Handle Problem Language Result Execution time Memory
89375 2018-12-12T16:24:34 Z vex Poklon (COCI17_poklon7) C++14
120 / 120
 385 ms 56464 KB 
#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.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 5 ms 796 KB Output is correct
12 Correct 6 ms 796 KB Output is correct
13 Correct 20 ms 2116 KB Output is correct
14 Correct 38 ms 3796 KB Output is correct
15 Correct 36 ms 3796 KB Output is correct
16 Correct 126 ms 9304 KB Output is correct
17 Correct 297 ms 19308 KB Output is correct
18 Correct 297 ms 21264 KB Output is correct
19 Correct 354 ms 21264 KB Output is correct
20 Correct 385 ms 56464 KB Output is correct