JOI 2011 春合宿 Guess Them All ( Binary Search, Interaction )

http://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day2.pdf
guess: 数当て (Guess Them All) - 2011年 日本情報オリンピック春合宿OJ | AtCoder
首先可以用 O( N )把 1的位置給找出來，接著對其他每個數字分別做區間的二分搜，找出它的位置。例如要找 2，可以先詢問左邊的區間 2222..1111，利用已經查出的 1位置推理我們現在想知道在哪個位置的 2是否在左邊。如果單純對每個數字做這樣的區間二分搜，實際的詢問次數最多會到 N + ( N - 1 ) lg( N )，會無法 AC，但是思考一下，什麼時候做了多餘的事，很容易想到例如只剩一個數字待猜，很明顯在哪裡，我們卻在區間亂搜。所以解決方法是，開一個可變長陣列紀錄待猜的位置，我們就只針對這些位置做二分搜，有一點離散的概念。這麼一來每猜一個數字就能減少區間的一個元素，詢問次數也將到 N + sum{ lg( k ) } Ɐ 1 ≤ k ≤ N。
不過這次我真的被這樣的輸入卡到快崩潰還渾然不覺 = =
input:
1
因為在我的 solve()裡，我默認 2必須存在，因此一開始線性猜測 1的位置的時候我都判斷當且僅當有 2個數對應到，才算是找到 1的位置。但事實上這會而且只會被序列長度為 1的時候卡到。到底怎麼會有這麼多 1的測資啊QQ。

這個 judge似乎會無視 assert()，以後我要使用它之前一定要記得先判斷這件事。後來用 TLE戰術耗了半個小時才終於找到問題。。我該反省一下，比起用這種雕蟲小技，應該要更清楚這種 corner case才對( 而且真要判的話應該判 corner case是否和錯的重疊，會比較省時 )。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 2;
const int MAXL = 700;

int n, pos[ MAXN ], num[ MAXN ];
vector<int> unknown;

int qry[ MAXN ];

int ask(){
    for(int i = 1; i <= n; ++i)
        printf("%d\n", qry[ i ]);
    fflush( stdout );
    int ret; scanf("%d", &ret);
    return ret;
}

void solve(){
    if( n == 1 ){
        qry[ 1 ] = 1;
        ask();
        return;
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            if( j == i ) puts("1");
            else puts("2");
        }
        fflush( stdout );
        int v; scanf("%d", &v);
        if( v == 2 ){
            pos[ 1 ] = i;
            num[ i ] = 1;
            break;
        }
    }
    for(int i = 1; i <= n; ++i){
        if( num[ i ] == 1 ) continue;
        unknown.push_back( i ); // which positions in answer array are remained unknown
    }
    for(int i = 2; i <= n; ++i){
        int lb = 0, rb = unknown.size();
        while( lb + 1 < rb ){
            int mid = ( lb + rb ) / 2;

            memset( qry, 0, sizeof(qry) );
            for(int j = lb; j < mid; ++j)
                qry[ unknown[ j ] ] = i;
            int one_is_counted = 0;
            for(int j = 1; j <= n; ++j)
                if( qry[ j ] == 0 ){
                    qry[ j ] = 1;
                    if( num[ j ] == 1 ) one_is_counted = 1;
                }

            bool is_left;
            if( ask() == 1 + one_is_counted ) is_left = true;
            else is_left = false;

            if( is_left ) rb = mid;
            else lb = mid;
        }
        pos[ i ] = unknown[ lb ];
        num[ unknown[ lb ] ] = i;
        // while( lb < 0 || lb >= unknown.size() );
        // while( unknown[ lb ] < 1 || unknown[ lb ] > n );
        // while( num[ unknown[ lb ] ] == 0 );
        unknown.erase( unknown.begin() + lb );
    }
    // while( unknown.size() == 1 );
    for(int i = 1; i <= n; ++i){
        printf("%d\n", num[ i ]);
        // while( num[ i ] == 0 );
    }
    fflush( stdout );
    int ret; scanf("%d", &ret);
    while( ret != n );
}

int main(){
    scanf("%d", &n);
    solve();
    return 0;
}