ABC 466 C - Count Close Pairs

[KATO-Hiro]

問題の感想や気づきを投稿・共有するスペースです

[moai199733]

いつもとサンプル形式が違うからデバッグが大変だった
配列と判定を自作すればサンプル以外も試しやすいんだなぁとなったし二分探索で書いてた時はこれで23回かかって回数オーバーしてた(1敗)
vector A = {0,1,3,4,5,7,9,10,12,15,20};
string Test(int i, int j){
if(A[j]-A[i] <= 1){
return "Yes";
} else {
return "No";
}
}

[primesosu91]

「質問が２N回まで」なので、O(N)の「尺取り法」を用いる。2分探索はO(N log N)となり間に合わない。インタラクティブな問題では"\n"ではなく、endlを使うことに気をつける。
C++

for(int l = 1; l < n; l ++){
    r = max(r, l + 1){
    while(r <= n){
        cout << "? " << l << " " << r << endl;
        string s;
        cin >> s;
        if(s == "Yes") r ++;
        else break;
    }
    ans += (r - l - 1);
}
cout << "! " << ans << endl;