QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#262579#7833. Binary StringEznibuilRE 0ms0kbC++141.4kb2023-11-23 20:35:112023-11-23 20:35:11

Judging History

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

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

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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Runtime Error

input:

252
237
124
19
69
22
9
160
23
127
124
99
125
127
110
60
46
5
109
75
113
11
63
62
61
33
30
59
17
33
31
32
13
14
28
14
17
15
30
20
13
15
17
14
8
1
9
8
9
7
4
8
3
6
5
5
2
3
2
1
0
2
2
2
2
1
1
1
4
2
2
0
1
0
1
1
1
1
1
1
1
1
0
1
0
0
0
1
0
4
4
3
1
2
4
3
1
1
1
5
3
3
3
0
1
1
3
2
0
2
1
0
1
5
1
1
2
3
2
0
6
4
4
0...

output:

? 1 500
? 501 1000
? 1 250
? 251 500
? 1 251
? 252 500
? 1 249
? 250 500
? 1 252
? 253 500
? 1 248
? 249 500
? 1 253
? 254 500
? 1 126
? 127 253
? 1 127
? 128 253
? 1 125
? 126 253
? 1 128
? 129 253
? 1 124
? 125 253
? 1 62
? 63 124
? 1 63
? 64 124
? 1 61
? 62 124
? 1 64
? 65 124
? 1 32
? 33 64
? 1 ...

result: