IOI 2016 Messy ( Interactive, Divide and Conquer )

http://ioinformatics.org/locations/ioi16/contest/day2/messy/messy-TWN.pdf
1960 - [IOI 2016] Messy | TIOJ INFOR Online Judge

題意：
你可以將任意數量的無號 n 位數丟 ( add_element() )進一個 set 裡面，然後呼叫 compile_set()，這個 set 裡面的所有數字都會依據一個未知的排列 p，以二進制表示，假設原本有個元素是 x*2^0+x*2^1+...+x*2^(n-1)，那麼該數會變成 x*2^p[0]+x*2^p[1]+...+x*2^p[n-1]。你接下來可以問 ( check_element() ) 任意的數是否存在在這個 set 裡。最後要回傳 p 陣列。

資料規模：
n ≤ 128，保證 n 是 2 的冪次
add_element() 和 check_element() 分別呼叫不超過 896 次。

解法：
保證 n 是 2 的冪次又長得很構造，一臉分治的。
排列本身不好求，轉個方向考慮「這個下標是誰要的」，formally 就是 P[] 的反函數。
對於一個下標 i，如果知道 i 是 [ lb, mid ) 其中一個人要的，那麼 i 一定不是 [ mid, rb ) 要的，反之亦然。
模糊地考慮，往 set 丟進 [ lb, mid ) 每個位置分別有 1 個 1，一共有 mid - lb 個元素。那麼，compile_set() 之後如果對於任意在 [ lb, rb ) 的 i 有元素是位置 i 為 1，那麼 P[ i ] 一定介於 [ lb, mid )。這樣掃過去後，就能分離好，使得左半邊的解和右半邊的解無關。持續遞迴做便能得解。 最後，為了區隔每層，沒有用到的部分都是設為 1。

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

void rec_add( string &s, int lb, int rb ){
  if( lb + 1 == rb ) return;
  int mid = lb + rb >> 1;
  for( int i = lb; i < mid; ++i ){
    s[ i ] = '1';
    add_element( s.c_str() );
    s[ i ] = '0';
  }
  {
    for( int i = mid; i < rb; ++i ){
      s[ i ] = '1';
    }
    rec_add( s, lb, mid );
    for( int i = mid; i < rb; ++i ){
      s[ i ] = '0';
    }
  }
  {
    for( int i = lb; i < mid; ++i ){
      s[ i ] = '1';
    }
    rec_add( s, mid, rb );
    for( int i = lb; i < mid; ++i ){
      s[ i ] = '0';
    }
  }
}

void rec_solve( string &s, vector< int > &pos, int lb, int rb ){
  if( lb + 1 == rb ) return;
  int mid = lb + rb >> 1;
  for( int i = lb, ptr = lb; i < rb; ++i ){
    s[ pos[ i ] ] = '1';
    bool chk = check_element( s.c_str() ); // debugged QQ
    s[ pos[ i ] ] = '0';
    if( chk ){
      swap( pos[ i ], p[ ptr++ ] );
    }
  }
  {
    for( int i = mid; i < rb; ++i ){
      s[ pos[ i ] ] = '1';
    }
    rec_solve( s, p, lb, mid );
    for( int i = mid; i < rb; ++i ){
      s[ pos[ i ] ] = '0';
    }
  }
  {
    for( int i = lb; i < mid; ++i ){
      s[ pos[ i ] ] = '1';
    }
    rec_solve( s, p, mid, rb );
    for( int i = mid; i < rb; ++i ){
      s[ pos[ i ] ] = '0';
    }
  }
}

void restore_permutation( int n, int w, int r, int* result ){
  {
    string s;
    for( int i = 0; i < n; ++i ){
       s += "0";
    }
    rec_add( s, 0, n );
    compile_set();
  }
  {
    string s;
    for( int i = 0; i < n; ++i ){
       s += "0";
    }
    vector< int > pos( n );
    for( int i = 0; i < n; ++i ){
      pos[ i ] = i;
    }
    rec_solve( s, pos, 0, n );
    for( int i = 0; i < n; ++i ){
      result[ pos[ i ] ] = i;
    }
  }
}