oj.uz

답안 #316155

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
316155 2020-10-25T15:36:20 Z Ahmad_Hasan Poklon (COCI17_poklon7) C++17
114 / 120
 364 ms 63992 KB 
#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.0 / 120.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 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 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 4 ms 640 KB Output is correct
13 Correct 17 ms 2304 KB Output is correct
14 Correct 34 ms 4344 KB Output is correct
15 Correct 32 ms 1920 KB Output is correct
16 Correct 115 ms 11644 KB Output is correct
17 Correct 271 ms 24952 KB Output is correct
18 Correct 274 ms 27256 KB Output is correct
19 Correct 331 ms 24568 KB Output is correct
20 Correct 364 ms 63992 KB Output is correct