QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#262616#7833. Binary StringEznibuilWA 242ms7496kbC++141.5kb2023-11-23 20:52:262023-11-23 20:52:27

Judging History

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

  • [2023-11-23 20:52:27]
  • 评测
  • 测评结果:WA
  • 用时:242ms
  • 内存:7496kb
  • [2023-11-23 20:52:26]
  • 提交

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<19)
	{
		int a=-1,b=-1;
		for(int i=0;i<1<<r-l;i++)
			if(__builtin_popcount(i)==s)
			{
				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;
	m.insert(query(0,(n>>1))+query((n>>1),n));
	for(int i=1;;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<<std::endl;
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 242ms
memory: 7496kb

input:

252
237
252
6
269
228
382
42
358
239
253
161
249
240
109
128
246
232
13
159
141
188
124
128
88
61
64
59
79
61
65
59
4
35
6
34
30
5
0
51
13
35
31
34
17
19
17
14
3
2
7
8
7
7
11
3
6
8
10
7
10
9
4
6
3
3
3
3
3
4
2
1
0
3
2
2
3
2
2
2
1
1
1
3
3
2
0
2
4
2
1
1
7
2
2
1
1
0
2
1
2
0
1
2
1
1
0
1
1
1
1
2
0
1
2
0
2...

output:

? 1 500
? 501 1000
? 1 501
? 502 1000
? 1 499
? 500 1000
? 1 502
? 503 1000
? 1 498
? 499 1000
? 1 503
? 504 1000
? 1 497
? 498 1000
? 1 250
? 251 500
? 1 251
? 252 500
? 1 249
? 250 500
? 1 252
? 253 500
? 1 248
? 249 500
? 1 124
? 125 248
? 1 125
? 126 248
? 1 123
? 124 248
? 1 126
? 127 248
? 1 6...

result:

wrong answer 1-st bit is incorrect. Expected 1, found: 0