QOJ上AC,luogu 29pts求条

//#include "shop.h"
#include<bits/stdc++.h>
int query(int *S, int nS, int *T, int nT);
int call(int *S,int nS,int *T,int nT){
	for(int i = 0; i < nS; i ++)
		S[i] --;
	for(int i = 0; i < nT; i ++)
		T[i] --;
	return query(S,nS,T,nT);
}
void set_a(int x,int y,int *ans){
	ans[x - 1] = y;
}
int a[5],b[5],ft[100009],cnt;
std :: queue<int>q;
void find_price(int task_id, int N, int K, int ans[]) {
	if(task_id == 3){//task 3,monotonic sequence
		 a[0] = 1;
		 b[0] = N;
		 if(call(a,1,b,1)){
		 	//puts("f0");
		 	int l = 0,r = N;
		 	while(l + 2 < r){
		 		int mid = (l + r) >> 1;
		 		a[0] = mid;
		 		a[1] = mid + 1;
		 		b[0] = N;
		 		if(call(a,2,b,1))
		 			l = mid;
		 		else
		 			r = mid + 1;
			 }
			 //printf("%d %d\n",l,r);
			 if(((N - r + 1) & 1) != K)
			 	set_a(r - 1,1,ans);
			else
				set_a(r - 1,0,ans);
			for(int i = 1; i <= l; i ++)
				set_a(i,0,ans);
			for(int i = r; i <= N; i ++)
				set_a(i,1,ans);
		 }
		 else{
		 	int l = 1,r = N + 1;
		 	while(l + 2 < r){
		 		int mid = (l + r) >> 1;
		 		a[0] = mid;
		 		a[1] = mid + 1;
		 		b[0] = 1;
		 		if(!call(a,2,b,1))
		 			l = mid;
		 		else
		 			r = mid + 1;
			 }
			 if(((l) & 1) != K)
			 	set_a(r - 1,1,ans);
			else
				set_a(r - 1,0,ans);
			for(int i = 1; i <= l; i ++)
				set_a(i,1,ans);
			for(int i = r; i <= N; i ++)
				set_a(i,0,ans);
		 }
	}
	else{
		while(!q.empty())
			q.pop();
		for(int i = 2; i <= N; i ++){
			q.push(i);
		}
		ft[cnt = 1] = 1;
		while(!q.empty()){
			int d = q.front();
			q.pop();
			if(!q.empty()){
				int e = q.front();
				q.pop();
				a[0] = d;
				a[1] = e;
				b[0] = ft[cnt];
				int x = call(a,2,b,1);
				b[0] = e;
				a[0] = d;
				int y = call(a,1,b,1);
				//printf("%d %d %d %d\n",d - 1,e - 1,x,y);
				if(x && y){
					set_a(d,0,ans);
					q.push(e);
				}
				else if(x && (!y)){
					set_a(e,0,ans);
					q.push(d);
				}
				else if((!x) && y){
					cnt ++;
					ft[cnt] = e;
					q.push(d);
				}
				else{
					cnt ++;
					ft[cnt] = d;
					q.push(e);
				}
			}
			else{
				if(cnt != 1){
					int e = ft[cnt - 1];
					a[0] = d;
					a[1] = e;
					b[0] = ft[cnt];
					int x = call(a,2,b,1);
					b[0] = e;
					a[0] = d;
					int y = call(a,1,b,1);
					//printf(" %d %d %d %d\n",d - 1,e - 1,x,y);
					if(x && y){
						set_a(d,0,ans);
					}
					else if(x && !y){
						set_a(e,0,ans);
						ft[cnt - 1] = d;
					}
					else if((!x) && (!y)){
						cnt ++;
						ft[cnt] = d;
					}
					else{
						int l = 0,r = cnt - 1;
						while(l + 1 < r){
							int mid = (l + r) >> 1;
							a[0] = ft[mid];
							b[0] = d;
							if(call(a,1,b,1))
								l = mid;
							else
								r = mid;
						}
						for(int i = cnt; i >= r; i --)
							ft[i + 1] = ft[i];
						ft[r] = d;
						cnt ++;
					}
				}
				else{
					a[0] = d;
					b[0] = ft[cnt];
					cnt ++;
					ft[cnt] = ft[cnt - 1];
					ft[1 + call(b,1,a,1)] = d;
				}
			}
		}
		 	int l = 0,r = cnt;
		 	while(l + 2 < r){
		 		int mid = (l + r) >> 1;
		 		a[0] = ft[mid];
		 		a[1] = ft[mid + 1];
		 		b[0] = N;
		 		if(call(a,2,b,1))
		 			l = mid;
		 		else
		 			r = mid + 1;
			 }
			 if(((cnt - r + 1) & 1) != K)
			 	set_a(ft[r - 1],1,ans);
			else
				set_a(ft[r - 1],0,ans);
			for(int i = 1; i <= l; i ++)
				set_a(ft[i],0,ans);
			for(int i = r; i <= cnt; i ++)
				set_a(ft[i],1,ans);
			//for(int i = 1; i <= cnt; i ++){
			//	printf("%d\n",ft[i] - 1);
			//}
	}
}
/*
3 3
15 100
000000011111111
15 100
111111111110000
15 100
111111111111111

3 1
15 100
110101101100000
15 100
001010110011000
15 100
011011100011011
*/