CFR 745 D. Hongcow's Game ( Binary Enumeration, Interactive )

Problem - D - Codeforces

題意：
有一個 N * N 的矩陣，裡面各自有 0 ~ 1e9 之間的整數，且對角線所有數值必為 0。你可以做詢問，用直列的編號們描述，對方會回答每個行分別對這些直列編號求的最小值。試用 20 次以內的詢問，得出所有行不含對角線的 0，分別的最小值。

資料規模：
2 ≤ N ≤ 1000
time limit: 3000 ms
memory limit: 256 MB

解法：
對於某個行 j，我們希望問 20 次以內，對那行的所有詢問裡的列編號的總集合裡不含 j 這個數字，但含所有除了 j 以外在範圍內的數字。想想 20，很像 2 * lg 1024，所以想想看分別枚舉各個位元為 1 的情形下，和為 0 的情形下，分別範圍內有哪些數字。這麼一來，假如二進位是 0110 這樣的數字，那麼就只要對第 0 位元為 1 的集合，第 1 位元為 0 的集合，第 2 位元為 0 的集合，第 3 位元為 1 的集合取和，就是所求。

時間 / 空間複雜度：
O( N lg N ) / O( N )

int N;

void init(){
  cin >> N;
}

vi ans;

void ask( const vi &qry, int bit, int has ){
  if( qry.empty() )
    return;
  cout << qry.size() << endl;
  for( int i = 0; i < qry.size(); ++i )
    cout << qry[ i ] + 1 << " \n"[ i + 1 == qry.size() ];
  for( int i = 0; i < N; ++i ){
    int v; cin >> v;
    if( ( has ? ~i : i ) >> bit & 1 )
      upmin( ans[ i ], v );
  }
}

void preprocess(){
  ans = vi( N, INF );
  for( int i = 0; i < 10; ++i ){
    vi qry;
    for( int j = 0; j < N; ++j )
      if( ~j >> i & 1 )
        qry.emplace_back( j );
    ask( qry, i, 0 );
    qry.clear();
    for( int j = 0; j < N; ++j )
      if( j >> i & 1 )
        qry.emplace_back( j );
    ask( qry, i, 1 );
  }
}

void solve(){
  cout << -1 << endl;
  for( int i = 0; i < N; ++i )
    cout << ans[ i ] << " \n"[ i + 1 == N ];
}