Submission #316158

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
316158	2020-10-25T15:46:53 Z	Ahmad_Hasan	Poklon (COCI17_poklon7)	C++17	114 / 120	385 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 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;
}

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%(1<<cntdpth)==0)?0:((1<<cntdpth)-(trg.first%(1<<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	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Incorrect	0 ms	384 KB	Output isn't correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	512 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	36 ms	4352 KB	Output is correct
15	Correct	33 ms	1920 KB	Output is correct
16	Correct	121 ms	11572 KB	Output is correct
17	Correct	288 ms	24952 KB	Output is correct
18	Correct	286 ms	27256 KB	Output is correct
19	Correct	346 ms	24568 KB	Output is correct
20	Correct	385 ms	63992 KB	Output is correct