QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#853621#9734. Identify Chorducup-team987#AC ✓63ms3748kbC++203.9kb2025-01-11 17:52:102025-01-11 17:52:16

Judging History

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

  • [2025-01-11 17:52:16]
  • 评测
  • 测评结果：AC
  • 用时：63ms
  • 内存：3748kb
查看
  • [2025-01-11 17:52:10]
  • 提交

answer

#include<iostream>
#include<cassert>
#include<random>
#include<cstdlib>
using namespace std;
mt19937 rng;
const bool debug=false;
int N,ansx,ansy,Qc;
int dist(int u,int v)
{
	u=(u%N+N)%N;
	v=(v%N+N)%N;
	if(u>v)swap(u,v);
	return min(v-u,u+N-v);
}
void init()
{
	Qc=0;
	N=rng()%((int)1e9-4+1)+4;
	while(true)
	{
		ansx=rng()%N;
		ansy=rng()%N;
		if(dist(ansx,ansy)>=2)break;
	}
	if(ansx>ansy)swap(ansx,ansy);
}
int ask(int u,int v)
{
	u=(u%N+N)%N;
	v=(v%N+N)%N;
	Qc++;
	if(debug)
	{
		return min(dist(u,v),min(dist(u,ansx)+1+dist(ansy,v),dist(u,ansy)+1+dist(ansx,v)));
	}
	else
	{
		cout<<"? "<<u+1<<" "<<v+1<<endl;
		int r;cin>>r;
		if(r<0)exit(0);
		return r;
	}
}
bool answer(int u,int v)
{
	u=(u%N+N)%N;
	v=(v%N+N)%N;
	if(debug)
	{
		if(u>v)swap(u,v);
		if(make_pair(u,v)!=make_pair(ansx,ansy))
		{
			cout<<"WA with query = "<<Qc<<endl;
			cout<<"ans = ("<<ansx<<", "<<ansy<<")"<<endl;
			cout<<"slv = ("<<u<<", "<<v<<")"<<endl;
			return false;
		}
		else
		{
			cout<<"AC with query = "<<Qc<<endl;
			if(Qc>40)return false;
			return true;
		}
	}
	else
	{
		cout<<"! "<<u+1<<" "<<v+1<<endl;
		int r;cin>>r;
		if(r<0)exit(0);
		return true;
	}
}
void solve2(int x,int y,int d0,int arc0)
{
	assert(abs(x-y)==1);
	//ask(x,N/2)-2==ask(y,N/2)
	int l=1,r=N/2+10;
	while(r-l>1)
	{
		int m=(l+r)/2;
		int p=x+(y-x)*m;
		if(2*m<d0&&ask(p,p+N/2)==d0-2*m)l=m;
		else r=m;
	}
	int p=x+(y-x)*l;
	int q=p+N/2;
	int d=d0-2*l;
	assert(d>=1);
	//assert(ask(p,q)==d);
	int arc=N/2-d+1;
	int arc2=N-N/2-d+1;
	//if(arc0!=-1)assert(arc==arc0||arc2==arc0);
	if(ask(p,p+arc)==1)
	{
		assert(answer(p,p+arc));
	}
	else if(ask(q,q-arc)==1)
	{
		assert(answer(q,q-arc));
	}
	else if(ask(q,q+arc2)==1)
	{
		assert(answer(q,q+arc2));
	}
	else if(ask(p,p-arc2)==1)
	{
		assert(answer(p,p-arc2));
	}
	else
	{
		assert(false);
	}
}
void solve3(int L,int R,int arc)
{
	assert(R-L>=arc);
	int l=L,r=R-arc+1;
	while(r-l>1)
	{
		int m=(l+r)/2;
		if(ask(m,R)==R-m-arc+1)l=m;
		else r=m;
	}
	assert(answer(l,l+arc));
}
void solve()
{
	if(N<=10)
	{
		for(int u=0;u<N;u++)for(int v=u+1;v<N;v++)
		{
			if(dist(u,v)>=2&&ask(u,v)==1)
			{
				assert(answer(u,v));
				return;
			}
		}
	}
	auto t=[&](int p)
	{
		int q=p+1;
		int d1=ask(p,p+N/2);
		int d2=ask(q,q+N/2);
		if(d1!=d2)
		{
			if(d1>d2)swap(d1,d2),swap(p,q);
			assert(d1<d2);
			if(d2-d1==1)solve2(q,p,d2+1,-1);
			else
			{
				assert(d2-d1==2);
				solve2(q,p,d2,-1);
			}
			return -1;
		}
		int r=q+1;
		int d3=ask(r,r+N/2);
		if(d2!=d3)
		{
			if(d2>d3)swap(d2,d3),swap(q,r);
			assert(d2<d3);
			if(d3-d2==1)solve2(r,q,d3+1,-1);
			else
			{
				assert(d3-d2==2);
				solve2(r,q,d3,-1);
			}
			return -1;
		}
		return d1;
	};
	int arc=t(0);
	if(arc==-1)return;
	int arc1=t(N/4);
	if(arc1==-1)return;
	int a=N/2-arc+1,aa=N-N/2-arc+1;
	int b=N/2-arc1+1,bb=N-N/2-arc1+1;
	if(a>=2&&a==bb&&ask(0,N/4+1)==N/4+1-a+1)
	{
		solve3(0,N/4+1,a);
	}
	else if(a>=2&&a==b&&ask(N/4,N/2+1)==N/2-N/4+1-a+1)
	{
		solve3(N/4,N/2+1,a);
	}
	else if(aa>=2&&aa==b&&ask(N/2,N/4+N/2+1)==N/4+1-aa+1)
	{
		solve3(N/2,N/4+N/2+1,aa);
	}
	else if(aa>=2&&aa==bb&&ask(N/4+N/2,N+1)==N-N/4-N/2+1-aa+1)
	{
		solve3(N/4+N/2,N+1,aa);
	}
	else
	{
		cout<<0<<" "<<N/4<<" "<<N/2<<" "<<N/4+N/2<<" "<<N<<endl;
		cout<<a<<" "<<aa<<" "<<b<<" "<<bb<<endl;
		cout<<dist(ansx,ansy)<<endl;
		cout<<ask(1,N/4)<<" "<<N/4-1-a+1<<endl;
		assert(false);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	if(debug)
	{
		for(N=4;;N++)
		{
			for(ansx=0;ansx<N;ansx++)for(ansy=ansx+1;ansy<N;ansy++)if(dist(ansx,ansy)>=2)
			{
				Qc=0;
				cout<<"N = "<<N<<", ans = ("<<ansx<<", "<<ansy<<")"<<endl;
				solve();
			}
		}
	}
	while(debug)
	{
		init();
		cout<<"N = "<<N<<", ans = ("<<ansx<<", "<<ansy<<")"<<endl;
		solve();
	}
	int T;cin>>T;
	for(;T--;)
	{
		cin>>N;
		solve();
	}
}
源文件, 语言: C++20

这程序好像有点Bug，我给组数据试试？

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3624kb

input:

2
6
2
2
2
1
1
4
1
1

output:

? 1 3
? 1 4
? 1 5
? 2 4
! 2 4
? 1 3
! 1 3

result:

ok ok (2 test cases)

Test #2:

score: 0
Accepted
time: 15ms
memory: 3680kb

input:

1000
15
5
5
5
5
5
7
5
5
1
1
19
5
3
1
1
1
17
5
3
1
1
1
15
6
7
6
6
1
1
14
5
5
7
5
5
1
1
15
3
1
1
1
17
8
8
6
2
3
3
3
1
1
20
6
8
6
6
1
1
13
5
6
3
3
4
4
1
1
18
3
3
5
3
5
5
1
1
13
4
4
4
6
6
5
3
3
4
1
1
14
2
4
3
3
1
1
17
8
6
4
4
5
1
1
12
5
3
1
1
1
10
2
3
4
5
4
3
2
2
3
4
5
4
3
2
2
3
4
3
4
3
2
3
2
3
4
2
1
1
...

output:

? 1 8
? 2 9
? 3 10
? 4 11
? 5 12
? 6 13
? 3 10
? 4 11
? 5 8
! 5 8
? 1 10
? 2 11
? 3 12
? 3 12
! 3 12
? 1 9
? 2 10
? 3 11
? 3 11
! 3 11
? 1 8
? 2 9
? 14 6
? 15 7
? 1 3
! 1 3
? 1 8
? 2 9
? 3 10
? 14 7
? 1 8
? 2 5
! 2 5
? 1 8
? 2 9
? 2 9
! 2 9
? 1 9
? 2 10
? 3 11
? 5 13
? 5 12
? 13 6
? 13 4
? 5 14
! 5 ...

result:

ok ok (1000 test cases)

Test #3:

score: 0
Accepted
time: 11ms
memory: 3620kb

input:

1000
21
3
5
1
1
1
22
8
6
4
4
7
7
7
1
1
20
5
5
5
7
9
5
5
1
1
22
10
8
4
4
7
1
1
21
9
7
5
5
6
1
1
21
8
8
8
10
10
9
7
7
7
4
1
1
24
11
12
5
7
5
5
8
8
1
1
22
10
10
11
10
10
2
2
1
1
21
4
2
3
3
3
1
1
23
8
8
8
8
8
10
8
8
4
4
1
1
21
10
10
8
4
4
7
1
1
24
9
7
7
7
6
1
1
20
9
10
9
9
9
2
2
1
1
24
11
11
11
11
11
11...

output:

? 1 11
? 2 12
? 21 10
? 21 10
! 21 10
? 1 12
? 2 13
? 4 15
? 3 14
? 3 11
? 14 6
? 14 22
? 3 17
! 3 17
? 1 11
? 2 12
? 3 13
? 6 16
? 7 17
? 4 14
? 5 15
? 5 11
! 5 11
? 1 12
? 2 13
? 4 15
? 5 16
? 4 12
? 15 7
! 15 7
? 1 11
? 2 12
? 4 14
? 3 13
? 3 9
? 13 7
! 13 7
? 1 11
? 2 12
? 3 13
? 6 16
? 7 17
? 8...

result:

ok ok (1000 test cases)

Test #4:

score: 0
Accepted
time: 6ms
memory: 3736kb

input:

1000
25
8
10
8
8
1
1
25
6
8
4
4
1
1
25
11
12
5
7
5
5
1
1
25
5
5
5
12
12
10
6
6
7
7
8
1
1
26
12
12
12
12
12
12
7
8
6
3
2
2
1
26
11
13
7
7
7
1
1
26
13
13
11
11
11
11
3
3
3
1
1
27
12
12
12
12
12
13
12
12
12
1
1
25
9
11
9
9
4
4
1
1
27
9
9
9
13
12
10
10
10
4
4
5
1
1
27
11
11
11
12
10
10
10
4
1
1
27
13
13...

output:

? 1 13
? 2 14
? 24 11
? 25 12
? 1 6
! 1 6
? 1 13
? 2 14
? 24 11
? 25 12
? 25 9
! 25 9
? 1 13
? 2 14
? 21 8
? 24 11
? 23 10
? 22 9
? 23 6
! 23 6
? 1 13
? 2 14
? 3 15
? 7 19
? 8 20
? 9 21
? 11 23
? 12 24
? 11 18
? 23 16
? 23 6
? 11 3
! 11 3
? 1 14
? 2 15
? 3 16
? 7 20
? 8 21
? 9 22
? 1 8
? 7 15
? 14 2...

result:

ok ok (1000 test cases)

Test #5:

score: 0
Accepted
time: 9ms
memory: 3676kb

input:

1000
29
10
8
6
6
9
9
10
1
1
28
13
14
3
3
1
1
30
3
1
1
1
29
4
4
6
4
1
1
28
8
10
6
6
9
9
1
1
29
6
4
2
3
3
3
1
1
29
9
9
9
13
14
9
9
9
6
6
1
1
28
11
11
11
11
13
11
11
11
1
1
30
4
6
4
7
7
1
1
30
8
10
6
6
6
10
10
1
1
28
11
9
9
9
6
1
1
29
14
14
14
13
13
13
7
4
2
2
1
29
11
11
11
12
12
12
5
3
4
1
29
7
9
7
7
...

output:

? 1 15
? 2 16
? 4 18
? 3 17
? 3 12
? 17 8
? 17 27
? 3 22
! 3 22
? 1 15
? 2 16
? 24 10
? 23 9
? 24 8
! 24 8
? 1 16
? 2 17
? 2 17
! 2 17
? 1 15
? 2 16
? 3 17
? 1 15
? 2 13
! 2 13
? 1 15
? 2 16
? 27 13
? 28 14
? 28 9
? 14 5
? 14 23
! 14 23
? 1 15
? 2 16
? 3 17
? 3 16
? 17 4
? 17 2
? 3 18
! 3 18
? 1 15
...

result:

ok ok (1000 test cases)

Test #6:

score: 0
Accepted
time: 7ms
memory: 3676kb

input:

1000
32
13
13
13
13
13
13
6
3
2
3
1
30
14
14
14
14
14
14
8
9
8
8
5
6
5
1
32
16
16
14
2
3
3
3
1
1
31
5
5
5
13
15
5
7
5
5
1
1
32
7
5
3
3
5
5
5
1
1
32
8
6
6
11
11
11
1
1
31
15
13
9
9
11
9
7
1
1
31
6
6
6
12
14
6
6
10
10
1
1
32
12
12
12
12
12
14
12
12
1
1
30
14
14
14
14
14
15
14
14
14
2
2
1
1
31
11
13
5
...

output:

? 1 17
? 2 18
? 3 19
? 9 25
? 10 26
? 11 27
? 1 10
? 4 10
? 5 10
? 6 10
! 5 9
? 1 16
? 2 17
? 3 18
? 8 23
? 9 24
? 10 25
? 1 9
? 8 17
? 16 24
? 23 2
? 27 2
? 25 2
? 26 2
! 26 28
? 1 17
? 2 18
? 3 19
? 9 25
? 9 24
? 25 10
? 25 8
? 9 26
! 9 26
? 1 16
? 2 17
? 3 18
? 8 23
? 9 24
? 2 17
? 5 20
? 4 19
? ...

result:

ok ok (1000 test cases)

Test #7:

score: 0
Accepted
time: 25ms
memory: 3616kb

input:

1000
34
17
16
10
10
10
8
8
8
1
1
33
8
8
8
14
16
8
8
8
1
1
33
11
11
11
13
15
11
11
11
11
6
6
1
1
34
11
13
5
5
1
1
34
11
9
9
9
9
9
9
1
1
35
14
16
14
14
14
1
1
34
8
10
4
6
4
1
1
34
14
12
6
6
11
11
11
1
1
34
16
16
16
16
16
16
8
5
6
5
1
33
9
9
9
16
14
8
8
8
9
1
1
33
16
16
15
15
15
15
2
1
1
34
16
16
16
16...

output:

? 1 18
? 2 19
? 8 25
? 5 22
? 6 23
? 5 13
? 22 14
? 22 30
? 5 31
! 5 31
? 1 17
? 2 18
? 3 19
? 9 25
? 10 26
? 3 19
? 6 22
? 5 21
? 6 15
! 6 15
? 1 17
? 2 18
? 3 19
? 9 25
? 10 26
? 3 19
? 6 22
? 8 24
? 7 23
? 8 14
? 24 18
? 24 31
! 24 31
? 1 18
? 2 19
? 32 15
? 31 14
? 32 11
! 32 11
? 1 18
? 2 19
? ...

result:

ok ok (1000 test cases)

Test #8:

score: 0
Accepted
time: 6ms
memory: 3620kb

input:

1000
36
18
17
17
17
17
2
1
1
36
3
5
3
5
5
1
1
36
13
13
13
13
13
13
5
3
2
3
1
36
5
5
5
18
17
5
5
9
9
9
1
1
36
18
17
9
11
9
9
10
10
10
1
1
36
12
10
8
8
8
11
1
1
35
13
13
13
16
14
12
12
12
12
6
1
1
36
13
11
9
9
9
10
1
1
36
14
12
6
4
4
7
7
7
1
1
36
16
16
16
18
18
16
16
16
16
3
3
3
1
1
36
9
7
1
1
1
36
8
...

output:

? 1 19
? 2 20
? 8 26
? 5 23
? 3 21
? 2 4
? 20 18
! 20 18
? 1 19
? 2 20
? 36 18
? 1 17
? 19 3
? 19 35
! 19 35
? 1 19
? 2 20
? 3 21
? 10 28
? 11 29
? 12 30
? 1 11
? 3 11
? 4 11
? 5 11
! 4 10
? 1 19
? 2 20
? 3 21
? 10 28
? 11 29
? 17 35
? 18 36
? 17 31
? 35 21
? 35 13
? 17 3
! 17 3
? 1 19
? 2 20
? 8 26...

result:

ok ok (1000 test cases)

Test #9:

score: 0
Accepted
time: 26ms
memory: 3612kb

input:

1000
37
17
18
7
11
9
7
12
12
1
1
36
17
17
17
17
17
17
10
10
9
5
3
2
2
1
38
9
9
9
15
17
9
9
9
9
1
1
37
15
13
11
11
11
11
8
1
1
37
12
14
12
12
7
7
1
1
36
8
8
8
18
18
16
8
10
8
8
11
1
1
37
6
6
6
18
18
17
5
5
9
1
1
37
18
18
17
5
3
3
5
5
5
1
1
37
17
18
17
17
17
2
2
1
1
37
8
6
4
4
7
1
1
37
10
10
10
14
16
...

output:

? 1 19
? 2 20
? 32 13
? 35 16
? 34 15
? 33 14
? 33 8
? 14 2
? 14 27
! 14 27
? 1 19
? 2 20
? 3 21
? 10 28
? 11 29
? 12 30
? 1 11
? 10 20
? 19 29
? 23 29
? 25 29
? 26 29
? 27 29
! 26 28
? 1 20
? 2 21
? 3 22
? 10 29
? 11 30
? 3 22
? 7 26
? 5 24
? 6 25
? 7 18
! 7 18
? 1 19
? 2 20
? 8 26
? 5 23
? 3 21
? ...

result:

ok ok (1000 test cases)

Test #10:

score: 0
Accepted
time: 6ms
memory: 3744kb

input:

1000
39
18
16
8
10
8
8
12
1
1
38
8
8
10
8
8
12
12
1
1
38
19
19
17
9
11
9
9
11
1
1
39
12
12
14
12
12
1
1
38
15
15
17
15
15
15
5
5
1
1
39
4
4
4
16
18
4
10
6
4
7
7
1
1
39
18
19
14
14
16
14
1
1
38
18
18
18
18
18
18
10
10
5
3
2
2
1
39
14
14
14
14
14
14
11
6
3
2
3
1
39
11
11
11
15
17
11
11
13
11
1
1
39
9
...

output:

? 1 20
? 2 21
? 9 28
? 5 24
? 7 26
? 6 25
? 6 18
? 25 13
! 25 13
? 1 20
? 2 21
? 3 22
? 37 18
? 1 20
? 2 14
? 21 9
? 21 33
! 21 33
? 1 20
? 2 21
? 3 22
? 10 29
? 6 25
? 8 27
? 7 26
? 7 18
? 26 15
! 26 15
? 1 20
? 2 21
? 3 22
? 38 18
? 1 20
? 2 10
! 2 10
? 1 20
? 2 21
? 3 22
? 33 14
? 37 18
? 1 20
? ...

result:

ok ok (1000 test cases)

Test #11:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

1000
40
12
10
4
2
3
1
1
40
18
16
6
10
6
6
11
1
1
40
15
13
11
11
11
10
10
10
1
1
40
8
10
8
8
1
1
40
16
16
16
16
16
16
11
11
7
6
6
5
1
40
15
17
3
9
5
3
5
5
1
1
41
13
15
13
13
1
1
40
7
7
7
20
19
7
13
9
7
13
1
1
40
18
18
18
18
18
18
11
11
9
7
7
8
1
40
6
6
6
20
20
18
6
12
8
6
11
11
11
1
1
40
4
4
6
4
1
1
...

output:

? 1 21
? 2 22
? 5 25
? 6 26
? 6 25
? 26 7
! 26 7
? 1 21
? 2 22
? 9 29
? 5 25
? 7 27
? 8 28
? 7 22
? 27 12
! 27 12
? 1 21
? 2 22
? 5 25
? 3 23
? 4 24
? 3 13
? 23 13
? 23 33
? 3 33
! 3 33
? 1 21
? 2 22
? 38 18
? 40 20
? 1 14
! 1 14
? 1 21
? 2 22
? 3 23
? 11 31
? 12 32
? 13 33
? 1 12
? 11 22
? 21 32
? ...

result:

ok ok (1000 test cases)

Test #12:

score: 0
Accepted
time: 10ms
memory: 3664kb

input:

1000
42
11
11
11
21
21
19
11
13
11
11
11
11
11
1
1
41
17
17
17
17
17
17
11
8
8
6
7
1
41
8
10
4
6
4
1
1
41
12
14
6
2
3
3
1
1
41
12
10
8
8
8
13
1
1
41
18
20
8
12
8
8
1
1
41
14
14
14
14
14
14
11
5
3
4
1
41
20
19
5
3
1
1
1
41
17
19
9
11
9
9
1
1
41
15
15
15
14
14
14
5
3
2
3
1
41
18
20
4
2
3
3
1
1
42
20
2...

output:

? 1 22
? 2 23
? 3 24
? 11 32
? 12 33
? 13 34
? 20 41
? 16 37
? 18 39
? 17 38
? 17 28
? 38 27
? 38 7
? 17 6
! 17 6
? 1 21
? 2 22
? 3 23
? 11 31
? 12 32
? 13 33
? 11 22
? 31 2
? 35 2
? 33 2
? 34 2
! 33 38
? 1 21
? 2 22
? 39 18
? 41 20
? 40 19
? 40 16
! 40 16
? 1 21
? 2 22
? 39 18
? 37 16
? 37 15
? 16 ...

result:

ok ok (1000 test cases)

Test #13:

score: 0
Accepted
time: 9ms
memory: 3680kb

input:

1000
43
4
4
4
20
21
6
4
4
1
1
42
18
18
18
18
18
18
11
9
5
5
4
1
43
6
6
6
18
20
6
12
8
6
1
1
43
18
20
4
2
3
3
1
1
43
21
21
19
15
15
17
15
7
7
8
1
1
43
17
19
7
11
7
7
1
1
43
18
18
18
19
19
19
8
7
6
7
1
43
21
21
21
21
21
21
12
6
3
2
1
1
42
13
13
13
21
21
19
13
13
13
13
9
1
1
42
20
20
20
21
20
20
20
20
...

output:

? 1 22
? 2 23
? 3 24
? 11 32
? 12 33
? 4 25
? 2 23
? 3 24
? 3 21
! 3 21
? 1 22
? 2 23
? 3 24
? 11 32
? 12 33
? 13 34
? 1 12
? 11 23
? 15 23
? 17 23
? 16 23
! 16 20
? 1 22
? 2 23
? 3 24
? 11 32
? 12 33
? 4 25
? 8 29
? 6 27
? 5 26
? 5 21
! 5 21
? 1 22
? 2 23
? 37 15
? 36 14
? 36 13
? 14 37
? 14 35
! 1...

result:

ok ok (1000 test cases)

Test #14:

score: 0
Accepted
time: 20ms
memory: 3620kb

input:

1000
44
22
22
20
14
14
14
14
9
9
9
1
1
44
11
9
3
3
5
5
5
1
1
43
11
11
11
18
16
10
10
10
10
12
1
1
43
21
21
20
12
14
12
12
10
1
1
44
19
17
17
17
17
6
6
6
1
1
44
16
16
16
16
16
16
6
3
2
3
1
44
17
19
13
13
15
13
10
10
1
1
44
10
8
6
6
6
11
1
1
43
13
15
9
11
9
13
13
1
1
43
4
4
6
4
7
7
1
1
44
9
9
9
19
21
...

output:

? 1 23
? 2 24
? 3 25
? 10 32
? 6 28
? 8 30
? 7 29
? 6 15
? 28 19
? 28 37
? 6 41
! 6 41
? 1 23
? 2 24
? 5 27
? 6 28
? 5 25
? 27 7
? 27 3
? 5 29
! 5 29
? 1 22
? 2 23
? 3 24
? 11 32
? 12 33
? 19 40
? 15 36
? 17 38
? 16 37
? 15 27
? 36 24
! 36 24
? 1 22
? 2 23
? 3 24
? 10 31
? 6 27
? 8 29
? 7 28
? 7 17
...

result:

ok ok (1000 test cases)

Test #15:

score: 0
Accepted
time: 13ms
memory: 3696kb

input:

1000
45
20
22
18
18
18
18
1
1
45
16
18
8
10
8
8
1
1
45
10
10
10
22
21
11
15
11
11
12
12
13
1
1
45
15
13
7
5
5
9
9
9
1
1
45
11
11
13
11
11
1
1
45
16
18
2
3
3
1
1
45
19
19
19
18
18
18
8
6
6
5
1
45
5
7
3
3
5
5
1
1
44
19
19
19
19
21
19
19
19
4
4
1
1
45
12
12
12
12
14
12
12
11
11
1
1
44
20
20
20
20
22
20...

output:

? 1 23
? 2 24
? 39 16
? 43 20
? 45 22
? 44 21
? 45 5
! 45 5
? 1 23
? 2 24
? 39 16
? 43 20
? 41 18
? 42 19
? 42 12
! 42 12
? 1 23
? 2 24
? 3 25
? 12 34
? 13 35
? 20 42
? 16 38
? 18 40
? 19 41
? 18 30
? 40 28
? 40 8
? 18 5
! 18 5
? 1 23
? 2 24
? 5 27
? 7 29
? 6 28
? 6 24
? 28 10
? 28 2
? 6 32
! 6 32
?...

result:

ok ok (1000 test cases)

Test #16:

score: 0
Accepted
time: 14ms
memory: 3624kb

input:

1000
46
18
16
8
4
4
7
1
1
46
9
7
3
3
5
5
5
1
1
46
22
20
10
12
10
10
14
14
14
1
1
46
19
19
19
19
19
19
8
4
4
3
1
46
5
7
5
5
1
1
46
21
19
7
11
7
7
13
1
1
46
18
16
8
6
6
11
1
1
46
16
14
8
10
8
15
1
1
46
22
22
23
22
22
22
22
2
2
1
1
46
5
3
3
5
5
5
1
1
45
19
19
19
19
19
21
19
19
19
4
4
1
1
46
14
16
6
6
6...

output:

? 1 24
? 2 25
? 6 29
? 8 31
? 9 32
? 8 28
? 31 11
! 31 11
? 1 24
? 2 25
? 4 27
? 5 28
? 4 25
? 27 6
? 27 2
? 4 29
! 4 29
? 1 24
? 2 25
? 10 33
? 6 29
? 8 31
? 7 30
? 7 21
? 30 16
? 30 44
? 7 39
! 7 39
? 1 24
? 2 25
? 3 26
? 12 35
? 13 36
? 14 37
? 1 13
? 5 13
? 7 13
? 6 13
! 6 11
? 1 24
? 2 25
? 45 ...

result:

ok ok (1000 test cases)

Test #17:

score: 0
Accepted
time: 47ms
memory: 3736kb

input:

1000
1000000000
499999999
499999999
499999999
499999999
499999999
499999999
250000001
250000001
250000001
250000000
125000001
187500000
156250000
140625000
132812500
128906250
126953126
127929689
128417969
128173829
128051759
127990724
127960206
127944948
127952578
127956392
127954485
127953531
1279...

output:

? 1 500000001
? 2 500000002
? 3 500000003
? 250000001 750000001
? 250000002 750000002
? 250000003 750000003
? 1 250000002
? 250000001 500000002
? 500000001 750000002
? 750000001 2
? 875000001 2
? 812500001 2
? 843750001 2
? 859375001 2
? 867187501 2
? 871093751 2
? 873046876 2
? 872070313 2
? 871582...

result:

ok ok (1000 test cases)

Test #18:

score: 0
Accepted
time: 39ms
memory: 3748kb

input:

1000
1000000000
499999969
499999969
499999969
499999969
499999969
499999969
250000001
249999970
124999985
62500024
93750020
109374987
101562488
97656239
95703145
96679708
97167958
96923818
96801748
96740744
96771231
96755972
96748374
96752158
96750251
96749297
96748851
96749090
96749178
96749119
967...

output:

? 1 500000001
? 2 500000002
? 3 500000003
? 250000001 750000001
? 250000002 750000002
? 250000003 750000003
? 1 250000002
? 250000001 500000002
? 374999986 500000002
? 437499978 500000002
? 406249982 500000002
? 390624984 500000002
? 398437483 500000002
? 402343732 500000002
? 404296857 500000002
? ...

result:

ok ok (1000 test cases)

Test #19:

score: 0
Accepted
time: 6ms
memory: 3624kb

input:

1000
1000000000
474148191
474148189
224148185
99148183
36648183
5398183
1491933
515371
27091
11833
4205
391
153
35
5
3
1
1
1
1000000000
479245617
479245619
229245613
104245611
41745611
10495611
2683111
729987
241707
119637
58603
28085
12827
5197
1383
429
191
73
13
7
3
1
1
1
1000000000
456055561
4560...

output:

? 1 500000001
? 2 500000002
? 125000004 625000004
? 187500005 687500005
? 218750005 718750005
? 234375005 734375005
? 236328130 736328130
? 236816411 736816411
? 237060551 737060551
? 237068180 737068180
? 237071994 737071994
? 237073901 737073901
? 237074020 737074020
? 237074079 737074079
? 237074...

result:

ok ok (1000 test cases)

Test #20:

score: 0
Accepted
time: 43ms
memory: 3620kb

input:

1000
1000000000
230485382
230485384
105485380
42985380
11735380
3922880
16630
1372
420
182
72
124
94
80
72
72
72
143
143
1
1
1000000000
237329401
237329399
112329397
49829397
18579397
2954397
1001273
24711
9453
1825
873
397
159
87
99
87
87
93
89
87
173
173
173
1
1
1000000000
311862190
311862192
6186...

output:

? 1 500000001
? 2 500000002
? 937500000 437500000
? 906250000 406250000
? 890625000 390625000
? 886718750 386718750
? 884765625 384765625
? 884757996 384757996
? 884757520 384757520
? 884757401 384757401
? 884757342 384757342
? 884757372 384757372
? 884757357 384757357
? 884757350 384757350
? 884757...

result:

ok ok (1000 test cases)

Test #21:

score: 0
Accepted
time: 47ms
memory: 3684kb

input:

1000
1000000000
288090905
288090905
288090905
295653197
295653199
288090905
288090905
288090905
288090905
288090905
288090905
291746947
289793823
288817261
288328979
288090905
288206909
288145875
288115357
288100099
288092469
288090905
288090905
288091517
288091041
288090905
288090923
288090905
2880...

output:

? 1 500000001
? 2 500000002
? 3 500000003
? 250000001 750000001
? 250000002 750000002
? 124999999 624999999
? 187500000 687500000
? 218750001 718750001
? 234375001 734375001
? 242187501 742187501
? 246093751 746093751
? 248046876 748046876
? 247070314 747070314
? 246582033 746582033
? 246337892 7463...

result:

ok ok (1000 test cases)

Test #22:

score: 0
Accepted
time: 37ms
memory: 3628kb

input:

1000
999999999
499999998
499999998
499999998
499999999
499999999
499999999
249999999
125000000
62500000
31250001
46875000
39062500
35156250
33203125
32226563
31738282
31494141
31372072
31433106
31402589
31387330
31379702
31383516
31381609
31380656
31381133
31381372
31381490
31381432
31381461
3138144...

output:

? 1 500000000
? 2 500000001
? 3 500000002
? 250000000 749999999
? 250000001 750000000
? 250000002 750000001
? 1 250000001
? 125000000 250000001
? 187500000 250000001
? 218750000 250000001
? 203125000 250000001
? 210937500 250000001
? 214843750 250000001
? 216796875 250000001
? 217773437 250000001
? ...

result:

ok ok (1000 test cases)

Test #23:

score: 0
Accepted
time: 63ms
memory: 3696kb

input:

1000
999999999
499999957
499999957
499999957
499999956
499999956
499999956
249999957
124999979
62499990
31250038
46875036
54687535
58593784
60546909
61523471
62011709
61767612
61889639
61828604
61798130
61813389
61821018
61824790
61822926
61823837
61823403
61823642
61823761
61823821
61823830
6182382...

output:

? 1 500000000
? 2 500000001
? 3 500000002
? 250000000 749999999
? 250000001 750000000
? 250000002 750000001
? 500000000 750000000
? 624999978 750000000
? 687499967 750000000
? 718749962 750000000
? 703124964 750000000
? 695312465 750000000
? 691406216 750000000
? 689453091 750000000
? 688476529 7500...

result:

ok ok (1000 test cases)

Test #24:

score: 0
Accepted
time: 27ms
memory: 3676kb

input:

1000
999999999
324545945
324545943
74545939
12045939
4233439
327189
83049
22015
6757
2943
1035
81
23
9
1
1
1
999999999
446446636
446446634
196446630
71446628
8946628
1134128
157566
35496
4980
1166
214
96
36
6
4
2
3
3
3
1
1
999999999
213858247
213858249
88858245
26358245
10733245
2920745
967621
47934...

output:

? 1 500000000
? 2 500000001
? 125000004 625000003
? 156250004 656250003
? 160156254 660156253
? 162109379 662109378
? 162231449 662231448
? 162261966 662261965
? 162269595 662269594
? 162271502 662271501
? 162272456 662272455
? 162272933 662272932
? 162272962 662272961
? 162272969 662272968
? 162272...

result:

ok ok (1000 test cases)

Test #25:

score: 0
Accepted
time: 29ms
memory: 3616kb

input:

1000
999999999
487015083
487015085
237015079
112015077
49515077
18265077
2640077
686953
198673
76603
15569
311
73
67
67
67
67
67
67
133
133
1
1
999999999
307120211
307120209
57120205
25870205
10245205
2432705
479581
235441
113371
52337
21819
6561
2747
839
363
125
47
65
47
51
47
47
47
93
1
1
99999999...

output:

? 1 500000000
? 2 500000001
? 874999998 374999998
? 812499997 312499997
? 781249997 281249997
? 765624997 265624997
? 757812497 257812497
? 756835935 256835935
? 756591795 256591795
? 756530760 256530760
? 756500243 256500243
? 756492614 256492614
? 756492495 256492495
? 756492466 256492466
? 756492...

result:

ok ok (1000 test cases)

Test #26:

score: 0
Accepted
time: 52ms
memory: 3696kb

input:

1000
999999999
265285129
265285127
249264885
249264885
249264885
249264885
249660127
249264885
249264885
249264885
249264885
249264885
249415987
249293917
249264885
249264885
249278659
249271031
249267217
249265309
249264885
249264885
249265071
249264953
249264893
249264885
249264885
249264887
24926...

output:

? 1 500000000
? 2 500000001
? 125000004 625000003
? 62500003 562500002
? 31250002 531250001
? 15625002 515625001
? 7812502 507812501
? 11718752 511718751
? 9765627 509765626
? 8789064 508789063
? 8300783 508300782
? 8056642 508056641
? 7934572 507934571
? 7995607 507995606
? 8026124 508026123
? 8010...

result:

ok ok (1000 test cases)

Test #27:

score: 0
Accepted
time: 40ms
memory: 3680kb

input:

1000
536870912
261621269
261621271
127403537
108355805
108355805
110626321
108355805
108355805
108529169
108355805
108355805
108355805
108398097
108355805
108365329
108355805
108357137
108355805
108355805
108356113
108355805
108355857
108355805
108355805
108355825
108355809
108355805
108355805
10835...

output:

? 1 268435457
? 2 268435458
? 469762047 201326591
? 436207614 167772158
? 452984831 184549375
? 461373439 192937983
? 457179135 188743679
? 459276287 190840831
? 460324863 191889407
? 459800575 191365119
? 460062719 191627263
? 460193791 191758335
? 460259327 191823871
? 460226559 191791103
? 460242...

result:

ok ok (1000 test cases)

Test #28:

score: 0
Accepted
time: 60ms
memory: 3740kb

input:

1000
536870911
244408485
244408485
244408485
244408485
244408485
244408485
134217729
110190759
73664570
82643070
68869225
66777647
65425764
65055916
64564899
64625483
64410267
64457291
64403487
64383365
64390036
64383311
64380002
64381630
64380789
64380369
64380159
64380054
64380001
64379975
6437998...

output:

? 1 268435456
? 2 268435457
? 3 268435458
? 134217728 402653183
? 134217729 402653184
? 134217730 402653185
? 134217728 268435457
? 402653183 2
? 457748562 2
? 430200872 2
? 443974717 2
? 450861639 2
? 447418178 2
? 449139908 2
? 448279043 2
? 448709475 2
? 448494259 2
? 448386651 2
? 448440455 2
? ...

result:

ok ok (1000 test cases)

Extra Test:

score: 0
Extra Test Passed
English 繁體中文 简体中文

服务器时间: 2025-02-01 19:48:53 | 开源项目