Submission #316151

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
316151	2020-10-25T15:27:15 Z	Ahmad_Hasan	Poklon (COCI17_poklon7)	C++17	114 / 120	363 ms	64504 KB

poklon

#include <bits/stdc++.h>

using namespace std;

vector<pair<long long,long long> >vps;
int cntdpth=1;
int cntbts(int n){
    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.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 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	39 ms	384 KB	Output is correct
5	Incorrect	1 ms	384 KB	Output isn't correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	1 ms	360 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	4 ms	768 KB	Output is correct
12	Correct	4 ms	640 KB	Output is correct
13	Correct	18 ms	3072 KB	Output is correct
14	Correct	34 ms	4396 KB	Output is correct
15	Correct	33 ms	1920 KB	Output is correct
16	Correct	116 ms	12664 KB	Output is correct
17	Correct	279 ms	26108 KB	Output is correct
18	Correct	281 ms	28408 KB	Output is correct
19	Correct	338 ms	25080 KB	Output is correct
20	Correct	363 ms	64504 KB	Output is correct