Atcoder ABC301 D Bitmaskが分かりません

Question

Atcoder ABC301 D Bitmaskが分かりません

https://atcoder.jp/contests/abc301/tasks/abc301_d
解説を参考に上から貪欲を行うコードを書いたのですが、WAになります。
以下のコードの間違っているところを教えてください。

前提

c++
上から貪欲を行っています。

該当のソースコード

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string S;
    long long N;
    cin >> S >> N;
    
    long long ans = 0;
    
    for (int i = 0; i < S.size(); i++) {
        if (S[i] == '1') {
            ans |= (1 << (S.size() - i - 1));
        } else {
            ans |= (0 << (S.size() - i - 1));
        }
    }
    
    if (ans > N) {
        cout << -1 << endl;
    } else {
        for (int i = 0; i < S.size(); i++) {
            if (S[i] == '?'){
                if((ans|(1 << (S.size() - i - 1))) <= N) {
                    ans |= (1 << (S.size() - i - 1));
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Answer 1

こちらの入力例を試してみてください。正しい出力は-1です。

10000000000000000000000000000000
1

念のため解説もしておきます。

C++で普通に1と書いた場合、int型(通常32bit)の1と解釈されます。
そのため、たいていの処理系では1 << 31は-2147483648となります。
(細かいことを言うと、範囲外までシフトした場合の動作は未定義)

今回の問題では、long long型(64bit以上)の1である必要があるので、1LLと書きましょう。
1LL << 31なら2147483648になります。

参考 : https://cpprefjp.github.io/lang/cpp11/long_long_type.html より引用

符号付き整数型であるlong longを表す整数リテラルには、llもしくはLLサフィックスを使用する。

Comments

[pond-e]

ありがとうございます！！