[AtCoder] ARC 078 E: Awkward Response

題目連結:http://arc078.contest.atcoder.jp/tasks/arc078_c

---

奇怪的二分搜題，賽中的時候我有想出來大概的方向，結果沒刻完QQ，賽後再刻才發現其實還滿討厭的，有一些小小的邊界case要想。
這裡我先二分搜出答案的位數，方法很簡單，就找一個字典序很小的數字10000000(這樣讀到Y就知道原因了)，然後開始搜尋他後面0的個數，因為顯然他的字典序比起來一定都會最小，那只要找到Y跟N之間的分界，那Y那個就會是位數。
第二步則是對每一位二分搜出他正確的值，這裡先讓數字超級巨大，這樣讀到Y或N時就知道原因了，所以就每次都選最一個是N的地方。
不過要注意一下，因為最後一次也還是N，所以要加回1讓他變成Y。
p.s 付個Judge用的code AC Code:

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;

int getDigit();
string getVal(int);

int main(){
	int dig = getDigit();
	string val = getVal(dig);
	long long ans=0;
	for(int i=0;i<dig;i++) ans=ans*10 + (val[i]-'0');
	cout<<"! "<<(ans+1)<<endl<<flush;
	return 0;
}

int getDigit(){
	int r=10, l=0;
	while(r-l > 1){
		int mid = (l+r)>>1;
		cout<<"? 1";
		for(int i=0;i<mid;i++) cout<<0;
		cout<<endl<<flush;
		char c;cin>>c;
		if(c=='Y') l=mid;
		else r=mid;
	}
	return l+1;
}

string getVal(int len){
	string ss="1000000000";
	for(int i=0;i<len;i++){
		int l=0, r=10;
		while(r-l>1){
			int mid=(l+r)>>1;
			ss[i]='0'+mid;
			cout<<"? "<<ss<<endl<<flush;
			char c;cin>>c;
			if(c=='Y') r=mid;
			else l=mid;
		}
		ss[i]='0'+l;
	}
	return ss;
}

Judge:

#include <bits/stdc++.h>
using namespace std;

int main(){
	default_random_engine rd(time(NULL));
	uniform_int_distribution<int> rg(1,1e9);
	int t=64;
	long long ans=rg(rd);
	stringstream jizz;jizz<<ans;
	string anss;jizz>>anss;
	while(t--){
		char c;cin>>c;
		long long x;cin>>x;
		if(c=='!'){
			cout<<((x==ans)?"AC":"WA")<<'\n';
			cout<<"You: "<<x<<'\n';
			break;
		}
		stringstream ss;ss<<x;
		string s;ss>>s;
		if(x<=ans and s<=anss) cout<<"Y"<<endl;
		else if(x>ans and s>anss) cout<<"Y"<<endl;
		else cout<<"N"<<endl;
	}
	if(t==0) cout<<"TLE"<<'\n';
	cout<<"> "<<ans<<'\n';
	return 0;
}