[TIOJ]1359. [Interactive]丟失的數

題目連結：http://tioj.ck.tp.edu.tw/problems/1359

你可以把每個數字加起來在看是少哪個數字，可是這樣會用太多Ask()。
不難觀察出來，把所有數字的第i位有幾個1找出來，那便可以找出丟失的數的那一位是1或0。
與第i位與丟失的數不同的數字便不可能是答案， 因此不用在 Ask()那個數字。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
#include "lib1359.h"
#define lld long long
#define PB push_back
#define F first
#define S second
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
using namespace std;
typedef pair<int,int> Pair;
vector<int> v,v2,v3;
bitset<105> ok;
int main(){
    int n = Initialize();
    int lo = 31 - __builtin_clz(n-1);
    int ans = 0;
    for(int i = 1; i < n ; i++)v.PB(i);
    for(int i = 0 ; i <= lo ; i++){
        int tmp = 0;
        v2.clear();v3.clear();
        for(int j = 0 ; j < n ; j++)if(!ok[j] && j&(1 << i))tmp++;
        for(int j : v){
            if(Ask(j,i+1))v2.PB(j);
            else v3.PB(j);
        }
        if(v2.size() == tmp){
            v = v3;
            for(int j = 0 ; j < n ; j++)if(j&(1 << i))ok[j] = 1;
        }else{
            v = v2;
            ans += (1 << i);
            for(int j = 0 ; j < n ; j++)if(!(j&(1 << i)))ok[j] = 1;
        }
    }
    Answer(ans);
    return 0;
}