C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 604K, 提交时间: 2019-09-26 16:53:35

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int INF=0x7f7f7f7f;
int L;

int check(int x)
{
    int ans=0,i=0;
    for(;i<31;++i)
        if(x&(1<<i))
            ++ans,L=max(i+1,L);
    return ans;
}

int lenz(ll x)
{
    for(int i=61;i>=0;--i)
        if(x&(1ll<<i)) return i+1;
    return 0;
}

int main()
{
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    a=check(a),b=check(b),c=check(c);
    if(a<b) swap(a,b);
    if(c>a+b) puts("-1");
    else if(c==a+b)
        printf("%d\n",(1<<c)-1);
    else
    {
        int d=a+b-c;
        ll ans=0;
        // debug2(a,b);
        // debug2(c,d);
        if(d>=a)
        {
            ++ans;
            for(int i=0;i<2*d-a-b;++i) ans<<=1;
            for(int i=0;i<a+b-d-1;++i) ans<<=1,++ans;
            ans<<=1;
        } else if(d>=b)
        {
            ++ans;
            for(int i=0;i<d-b;++i) ans<<=1;
            for(int i=0;i<b-1;++i) ans<<=1,++ans;
            ans<<=1;
            for(int i=0;i<a-d;++i) ans<<=1,++ans;
        } else
        {
            for(int i=0;i<d;++i) ans<<=1,++ans;
            ans<<=1;
            for(int i=0;i<a+b-2*d;++i) ans<<=1,++ans;
        }
        // debug2(L,ans);
        if(lenz(ans)<=L) printf("%lld\n",ans);
        else puts("-1");
    }
    return 0;
}

/*==================================================================
added at 2019-09-26 15:51:55 P4574
第一次做自己推了一个60^4的dp公式,后来发现不能把a和b的1混起来用
所以还是换构造的方法重新做一遍
没有考虑到d>=a的那个情况
==================================================================*/

Python3(3.9) 解法, 执行用时: 41ms, 内存消耗: 6868K, 提交时间: 2021-05-07 19:34:32

def bin_count(x):
    bin_n = 0
    one_n = 0
    while x > 0:
        if (x & 1) == 1:
            one_n += 1
        bin_n += 1
        x >>= 1
    return bin_n, one_n

def solve(a, b, c):
    an, a1 = bin_count(a)
    bn, b1 = bin_count(b)
    cn, c1 = bin_count(c)
    if a1 < b1:
        bn, an = an, bn
        b1, a1 = a1, b1

    ans = -1
    if c1 == 0:
        if a1 + b1 == 0:
            ans = 0
    elif a1 + b1 == c1:
        ans = 0
        while c1 > 0:
            ans = (ans << 1) | 1
            c1 -= 1
    elif a1 + b1 > c1:
        k = a1 + b1 - c1
        t1 = min(k - 1, a1 - 1)
        t2 = k - 1 - t1
        y = min(a1 - t1 - 1, t2) + min(b1 - t2 - 1, t1)
        x = k - 1 - y
        z = a1 + b1 - y - k - 1
        if x + y + z + 2 <= max(an, bn, cn):
            ans = 1
            for i in range(x):
                ans <<= 1
            for i in range(y):
                ans = (ans << 1) | 1
            ans <<= 1
            for i in range(z):
                ans = (ans << 1) | 1

    print(ans)


if __name__ == '__main__':
    a, b, c = map(int, input().split())
    solve(a, b, c)

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 504K, 提交时间: 2020-02-14 16:06:20

#include<cstdio> 
#include<iostream> 
using namespace std; 
int calc(int x){ 
    int t=0; for (; x; x>>=1) t++; return t;  
}
int getit(int x){ 
    int t=0; for (; x; x^=x&-x) t++; return t; 
}
int main(){
    int a,b,c; scanf("%d%d%d",&a,&b,&c); 
    int len=max(max(calc(a),calc(b)),calc(c)),ans; 
    a=getit(a); b=getit(b); c=getit(c);  
    if (a>b) swap(a,b); 
    if (c<=a) ans=(1<<(a+b-c))|((1<<c)-2); 
    else if (c<=b) ans=((1<<b)|((1<<c)-1))^(1<<(c-a)); 
    else if (c<=a+b) ans=((1<<(c+1))-1)^(1<<(c+c-a-b)); 
    else {puts("-1"); return 0;  } 
    printf("%d\n",(calc(ans)<=len)?ans:-1); 
    return 0; 
}