Submission #316162

#	Time	Username	Problem	Language	Result	Execution time	Memory
316162		Ahmad_Hasan	Poklon (COCI17_poklon7)	C++17	114 / 120	375 ms	63992 KiB

poklon

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<pair<long long,long long> >vps;
int cntdpth=1;
int cntbts(int n){
    if(n==0)
        return 1ll;
    int ret=0ll;
    while(n){
        ret++;
        n>>=1;
    }
    return ret;
}
pair<int,int> maxx(pair<int,int> b1,pair<int,int> b2){
    int sz1=cntbts(b1.first);
    int sz2=cntbts(b2.first);
    if(sz1+b1.second>sz2+b2.second)
        return b1;
    if(sz1+b1.second<sz2+b2.second)
        return b2;
    if(b1.second>b2.second)
        swap(b1,b2);
    int nb1=b1.first;
    int nb2=b2.first;
    while(sz1<sz2) {
            sz1++;
            nb1*=2;
    }
    while(sz1>sz2){
        sz2++;
        nb2*=2;
    }

    if(nb1>nb2)
    return b1;
    else
        return b2;
}

pair<int,int> trg;
pair<int,int> slvmx(int cr=0,int dpth=1){
    cntdpth=max(cntdpth,dpth);
    pair<int,int> mx;
    mx={0,0};
    if(vps[cr].first<=0){
        pair<int,int> binary ; //"00000000000000000000000010000000"
        binary.first=vps[cr].first*-1ll;
        binary.second=0;
        mx=maxx(mx,binary);
    }else{
        pair<int,int> ret=slvmx(vps[cr].first-1,dpth+1);
        if(ret.first!=0)
        ret.second++;
        mx=maxx(mx,ret);
    }
    if(vps[cr].second<=0){
        pair<int,int> binary ; //"00000000000000000000000010000000"
        binary.first=vps[cr].second*-1ll;
        binary.second=0;
        mx=maxx(mx,binary);
    }else{
        pair<int,int> ret=slvmx(vps[cr].second-1,dpth+1);
        if(ret.first!=0)
        ret.second++;
        mx=maxx(mx,ret);
    }
    return mx;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);      cout.tie(0);
    int n;
    cin>>n;
    vps=vector<pair<long long,long long> >(n);
    for(int i=0;i<n;i++){
        long long x,y;
        cin>>x>>y;
        vps[i]={x,y};
    }
    trg=slvmx();
     if(trg.first!=0)
        trg.second++;
    if(cntdpth>trg.second){
        cntdpth-=trg.second;
        trg.first+=((trg.first%(1ll<<cntdpth)==0ll)?0ll:(long long)((1<<cntdpth)-(trg.first%(1ll<<cntdpth))));
    }
    string binary = std::bitset<64>(trg.first).to_string();
        binary.erase(0, binary.find_first_not_of('0'));
    if(binary.size()==0)
        binary="0";
    cout<<binary;
    while(trg.second--) cout<<'0';
    return 0;
}

/***
2
-10 2
-4 -3

*/

• Subtask 1: 114 / 120