Submission #316162

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
316162	2020-10-25T15:55:15 Z	Ahmad_Hasan	Poklon (COCI17_poklon7)	C++17	114 / 120	375 ms	63992 KB

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.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Incorrect	0 ms	384 KB	Output isn't correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	4 ms	768 KB	Output is correct
12	Correct	5 ms	640 KB	Output is correct
13	Correct	18 ms	2304 KB	Output is correct
14	Correct	38 ms	4352 KB	Output is correct
15	Correct	32 ms	1920 KB	Output is correct
16	Correct	119 ms	11640 KB	Output is correct
17	Correct	286 ms	25080 KB	Output is correct
18	Correct	282 ms	27392 KB	Output is correct
19	Correct	340 ms	24440 KB	Output is correct
20	Correct	375 ms	63992 KB	Output is correct