Codeforces #1046 : Div1. D2. From the Unknown (Hard Version)

このテキストボックス埋めの題材、Codeforcesでしか見たことないかも。
https://codeforces.com/contest/2135/problem/D2

問題

テキストボックスの幅Wを当てるinteractive問題である。
以下のクエリを2回だけ用いてWを当てよ。

クエリでは単語長のリストを指示する。
テキストボックスにその単語群を並べるとき、単語の途中でテキストボックスの幅に収まりきらない場合、その単語は次の行に送られる。
そうして計算された、必要な行数が与えられる。

解法

平方分割の要領で解く。

初回で、(130をi回並べた後に140を並べる)という単語列をi=0～139まで繰り返して連結する。
この結果からある程度長さを絞れる。
2回目では、その範囲内で長さを特定していく。

int T;
int W;
int table[144];

int ask2(int W,vector<int> V) {
	int L=1,S=0;
	FORR(v,V) {
		assert(v>=1&&v<=100000);
		if(v>W) return 1<<20;
		if(S+v>W) L++, S=0;
		S+=v;
	}
	return L;
}

int ask(vector<int> V) {
	if(W) {
		int ret=ask2(W,V);
		if(ret==1<<20) return 0;
		return ret;
	}
	cout<<"? "<<V.size();
	FORR(v,V) {
		assert(v>=1&&v<=100000);
		cout<<" "<<v;
	}
	cout<<endl;
	int x;
	cin>>x;
	return x;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	vector<int> V={},V2={};
	FOR(i,140) {
		FOR(j,i) V.push_back(130);
		V.push_back(140);
	}
	FOR(i,160) {
		FOR(j,i) V2.push_back(1+j%2);
		V2.push_back(2);
	}
	
	for(i=2;i<=140;i++) table[i]=ask2(i,V2);
	
	
	
	cin>>T;
	while(T--) {
		//cin>>W;
		k=ask(V);
		
		if(k==0) {
			k=ask(V2);
			for(i=1;i<=140;i++) {
				if(table[i]==k) {
					cout<<"! "<<i<<endl;
					break;
				}
			}
			continue;
		}
		
		
		x=y=0;
		for(i=18;i>=0;i--) {
			if(ask2(x+(1<<i),V)>=k) x+=1<<i;
			if(ask2(y+(1<<i),V)>k) y+=1<<i;
		}
		y++;
		if(x>=100000) x=100000;
		
		if(x==y) {
			cout<<"! "<<x<<endl;
		}
		else {
			assert(x<y*2);
			vector<int> C;
			for(i=y+1;i<=x;i++) {
				C.push_back(y);
				C.push_back(i-y);
			}
			k=ask(C);
			int ret=x-(k-C.size()/2);
			cout<<"! "<<ret<<endl;
		}
		
	}
}

まとめ

想定解とは違うが、まぁ解けて良かった。