[TIOJ] 1839. [IOI 2013] 洞穴 Cave

題目連結:http://tioj.infor.org/problems/1839

---

經典的二分搜題，對於每個門都二分搜一次他的開關是哪一個，記錄下來並使他保持開著的狀況，如此便可以往下繼續走下去，一次檢驗出一個門，所以複雜度是$O(n^2 log n)$，不過該怎麼二分搜呢?不妨每次都反轉一串開關(已知道的就不要轉)，看結果有沒有變成跟上一次不一樣(這裡的不一樣指的是說有沒有動到你要問的那個人)，也就是說如果按下去發現原本只能通到i，但現在可以走到i+1之類的，那你剛剛必定按到i了，反之如果現在可以到達i+1你按完之後只能到i那，也是有按到的，所以依此性質就可以二分搜每個門對應到的開關是誰，同時也知道如何開關才好。
p.s沒看到多筆測資害我被梗了一下下ww

#include "lib1839.h"
#define N 5000

int MAP[N+5], OPENED[N+5];
inline void SWAP(int,int);

int main(){
	while(1){
		int n=Initialize();
		for(int i=0;i<n;++i) MAP[i]=-1;
		for(int i=0;i<n;++i){
			int sks = tryCombination(OPENED);if(sks==-1)sks=n;
			bool preSAME = (sks==i);
			int l=0, r=n;bool ff=(sks>i);
			while(r-l>1){
				int mid=(l+r)/2;
				SWAP(l,mid);
				int kawaii=tryCombination(OPENED);if(kawaii==-1)kawaii=n;
				bool curSAME = (kawaii==i);
				if(curSAME==preSAME) l=mid;
				else r=mid;
				ff=(kawaii>i);
				preSAME=curSAME;
			}
			MAP[l]=i;
			if(!ff) OPENED[l]=(OPENED[l]+1)&1;
		}
		answer(OPENED,MAP);
	}
	return 0;
}

inline void SWAP(int l,int r){
	for(int i=l;i<r;++i) if(MAP[i]==-1) OPENED[i]=(OPENED[i]+1)&1;
}

C++