QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#262575#7833. Binary StringEznibuilTL 0ms0kbC++141.4kb2023-11-23 20:33:482023-11-23 20:33:48

Judging History

你现在查看的是最新测评结果

  • [2023-11-23 20:33:48]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-11-23 20:33:48]
  • 提交

answer

#include<cstring>
#include<iostream>
#include<set>
constexpr int n=1000;
bool ans[n];
int q[n][n];
int query(int l,int r)
{
	if(~q[l][r-1])
		return q[l][r-1];
	std::cout<<'?'<<l+1<<' '<<r<<std::endl;
	int x;
	std::cin>>x;
	return q[l][r-1]=x;
}
void dfs(int s,int l,int r)
{
	if(r-l<16)
	{
		int a=-1,b=-1;
		for(int i=0;i<1<<r-l;i++)
		{
			int x=0,y=0;
			for(int j=l;j<r;j++)
				for(int k=r;k>j;k--)
					if(y++,__builtin_popcount(i>>j-l&(1<<k-j)-1)==query(j,k))
						x++;
			if(b<std::abs((y>>1)-x))
				a=i,b=std::abs((y>>1)-x);
		}
		for(int i=l;i<r;i++)
			ans[i]=a>>i-l&1;
		return;
	}
	for(int i=0;;i++)
	{
		int x=query(l,(l+r>>1)+i),y=query((l+r>>1)+i,r);
		if(x+y==s)
		{
			dfs(x,l,(l+r>>1)+i),dfs(y,(l+r>>1)+i,r);
			break;
		}
		x=query(l,(l+r>>1)-i),y=query((l+r>>1)-i,r);
		if(x+y==s)
		{
			dfs(x,l,(l+r>>1)-i),dfs(y,(l+r>>1)-i,r);
			break;
		}
	}
	return;
}
int main()
{
	std::cin.tie(nullptr)->sync_with_stdio(0);
	std::memset(q,0xff,sizeof(q));
	std::set<int>m;
	for(int i=0;;i++)
	{
		int x=query(0,(n>>1)+i)+query((n>>1)+i,n);
		if(m.count(x))
		{
			dfs(x,0,n);
			break;
		}
		m.insert(x),x=query(0,(n>>1)-i)+query((n>>1)-i,n);
		if(m.count(x))
		{
			dfs(x,0,n);
			break;
		}
		m.insert(x);
	}
	std::cout<<"! ";
	for(int i=0;i<n;i++)
		std::cout<<ans[i];
	std::cout.flush();
	return 0;
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:


output:

?1 500

result: