oj.uz

답안 #316158

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

# 결과 실행 시간 메모리 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