らての精進日記

修行をします

joi春合宿2014 day1-4:Ramen

解法

N回のCompareで最大or最少のラーメン屋を見つけることが出来るので、2*N回で答えが出るしやるだけでは、と思ったら600回しか質問が出来なくて焦った。

まず、N軒のラーメン屋を2軒ずつペアにして、それぞれについて比較する(N/2回のCompare)

すると、任意のペアについて、こってり度が高かったほうはこってり度最少にはなることが不可能で、逆も同様に不可能だということが言える。
そこで、こってり度が高いグループと低いグループに分ける(N/2軒のラーメン屋の集合が二つ)

こってり度が高いグループのなかでこってり度が最大のラーメン屋を探す(N/2回のCompare)
逆もやる(N/2回のCompare)

これで答えが求まる。
CompareはN*3/2回なので大体600回。

コード

#include<bits/stdc++.h>
#include"ramen.h"
using namespace std;

void Ramen(int N){
    if(N==1){
        Answer(0,0);
        return;
    }

    vector<int>win,lose;
    for(int i=0;i<N/2;i++){
        if(Compare(i*2,i*2+1)==1){
            win.push_back(i*2);
            lose.push_back(i*2+1);
        }
        else{
            win.push_back(i*2+1);
            lose.push_back(i*2);
        }
    }
    if(N&1){
        win.push_back(N-1);
        lose.push_back(N-1);
    }

    int ma=0,mi=0;
    for(int i=1;i<win.size();i++){
        assert(win[i]!=win[ma]);
        if(Compare(win[i],win[ma])==1)ma=i;
    }

    for(int i=1;i<lose.size();i++){
        assert(lose[mi]!=lose[i]);
        if(Compare(lose[mi],lose[i])==1)mi=i;
    }

    Answer(lose[mi],win[ma]);
}