Submission #316155

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

poklon

#include <bits/stdc++.h>

using namespace std;

vector<pair<long long,long long> >vps;
int cntdpth=1;
int cntbts(int n){
    if(n==0)
        return 1;
    int ret=0;
    while(n){
        ret++;
        n>>=1;
    }
    return ret;
}
pair<int,int> maxx(pair<int,int> b1,pair<int,int> b2){
    int sz1=cntbts(b1.first)+b1.second;
    int sz2=cntbts(b2.first)+b2.second;
    if(sz1>sz2)
        return b1;
    if(sz1<sz2)
        return b2;
    if(b1.second>b2.second)
        swap(b1,b2);
    int nb2f=b2.first<<(b2.second-b1.second);
    if(b1.first>nb2f)
    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*-1;
        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*-1;
        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;
}

int 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%(1<<cntdpth)==0)?0:((1<<cntdpth)-(trg.first%(1<<cntdpth))));
    }
    string binary = std::bitset<32>(trg.first).to_string(); //"00000000000000000000000010000000"
        binary.erase(0, binary.find_first_not_of('0')); //"10000000"
    if(binary.size()==0)
        binary="0";
    cout<<binary;
    while(trg.second--) cout<<'0';
    return 0;
}

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

*/

• Subtask 1: 114 / 120