隱形史萊姆探測

題目描述

你是一個史萊姆農場的實習生。農場裡有 $N$ 個籠子排成一列（編號從 $1$ 到 $N$）。 昨天晚上農場發生了魔力外洩，導致其中 $K$ 隻史萊姆變成了隱形狀態。 空籠子依然是空的，但你肉眼看不出哪些籠子裡有隱形史萊姆。

不過你手邊有一台區間探測儀。 每次你可以設定一個探測區間 $[L, R]$，探測儀會掃描從第 $L$ 個籠子到第 $R$ 個籠子，並且精準地告訴你這個區間內總共有幾隻隱形史萊姆。

你的任務是：用最少的探測次數，找出所有隱形史萊姆所在的籠子編號。

互動方式

這是一道互動題。程式開始時，請從標準輸入讀取一個整數 $N$，代表總籠子數量。（注意：除了一些特定的子任務外，你一開始不會知道 $K$ 是多少）。

你可以透過標準輸出發起詢問，格式如下： ? L R （代表你要探測從 $L$ 到 $R$ 的區間。必須滿足 $1 \le L \le R \le N$） 注意輸出後要cout << endl;不然他會死掉。

發出詢問後，請從標準輸入讀取一個整數 $X$，代表該區間內隱形史萊姆的數量。

當你確信找出了所有有隱形史萊姆的籠子時，請輸出： ! K ans_1 ans_2 ... ans_K （先輸出一個驚嘆號 !，接著輸出一個整數 $K$ 代表你找到的數量，最後輸出所有有隱形史萊姆的籠子編號，編號必須由小到大排序，以空白分隔），然後立刻結束程式。

子任務與配分 (共 27 個測試點)

你的詢問次數不能超過該測資的上限 $Q_{max}$。

• 【$\mathbf{10}$%】(Test 1~3) $N \le 1000$，$K$ 未知。$Q_{max} = 1000$。

• 【$\mathbf{20}$%】(Test 4~7) $N = 100000$。保證 $K = 1$。$Q_{max} = 18$。

• 【$\mathbf{20}$%】(Test 8~11) $N = 100000$。保證 $K = 2$。$Q_{max} = 34$。

• 【$\mathbf{20}$%】(Test 12~16) $N = 100000$，$K \le 15$。$Q_{max} = 300$。

• 【$\mathbf{20}$%】(Test 17~21) $N = 100000$，$K \le 50$。$Q_{max} = 650$。

• 【$\mathbf{10}$%】(Test 22~26) $N = 100000$，$K \le 5000$。$Q_{max} = 30000$。

  可以拿到10分的程式:

  #include<bits/stdc++.h>
  using namespace std;
  int main(){
      int n;
      cin >> n;
      int m;
  	vector<int>ve;
      for(int i = 1; i<= n; i++){
      	cout <<"? " << i << " " << i;
      	cout << endl;
    	cin >> m;
    	if(m == 1){
    		ve.push_back(i);
    	}
    }
    cout <<"! " << ve.size();
    for(int i = 0; i < ve.size(); i++){
    	cout << " " << ve[i];
    }
    cout << endl;
  }